코테/백준

📖 문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 💡 풀이 방식 • 부분 집합 (백트래킹, 재귀) + BFS 필요 자료구조 [전역변수] - 인구 수 저장용 1차원 int형 배열 - 그래프 정보를 저장하기 위한 그래프 리스트 배열 - 부분 집합용 사용 여부 표시용 1차원 boolean형 배열 - 최솟값 [BFS용] - 방문할 원소를 저장하는 Integer형 큐 - 방문 표시용 1차원 boolean형 배열 (연결되었는지 확인용) [두 그룹에 속한 원소들 저장하고, 차이 저장용] - 구역A 원소들 저장할 Integer형 리스트 -..

📖 문제 1394번: 암호 첫 번째 줄에는 암호로 사용할 수 있는 문자가 공백 없이 주어지고, 두 번째 줄에는 컴퓨터의 암호가 주어진다. 암호에 사용할 수 있는 문자의 종류는 최대 100가지이고, 공백은 사용할 수 없다. www.acmicpc.net 💡 풀이 방식 • 문자열 1차원 배열에 해당 문자가 첫 번째로 쓰인 순서를 기록한다. (배열 인덱스에 매핑 시 아스키코드 상 '!'가 가장 작은 수의 문자라 활용) 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import java.util.*; import java.io.*; public class Main { s..

📖 문제 23352번: 방탈출 첫줄에 지도의 세로 크기 $N$($1 \le N \le 50$), 가로 크기 $M$($1 \le M \le 50$)이 공백을 두고 주어진다. 둘째 줄부터 $N$줄에 걸쳐 각 방들의 정보 $A$($0 \le A \le 9$)가 공백을 두고 주어진다. www.acmicpc.net 💡 풀이 방식 • BFS 상하좌우로 이동하며 가장 긴 경로 길이인 시작점과 끝점의 합을 구한다. 4방향 탐색 후, 현재 이동 거리가 최대 이동거리보다 길다면 최대 이동거리 len을 변경하고, 시작 방과 끝 방에 적힌 숫자의 합을 구해 최댓값 max와 비교해 갱신한다. if(!flag && now[2] >= len) { // 현재 이동 거리가 최대 이동거리보다 많으면 최대 이동거리 변경 if(now[2]..

📖 문제 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net 💡 풀이 방식 • 구현 1. 단어 맨 뒤에서부터 확인하며 처음으로 감소하는 부분의 인덱스를 찾는다. (idx1) 2. 다시 맨 뒤에서부터 확인하며 감소하는 부분보다 큰 부분의 인덱스를 찾는다. (idx2) 3. idx1과 idx2에 있는 두 값을 swap한다. 4. 단어의 idx1 위치부터 끝까지 단어를 오름차순 정렬한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..

📖 문제 17213번: 과일 서리 민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. www.acmicpc.net 💡 풀이 방식 • DP 1. M*M 크기의 2차원 배열 dp를 만든다. dp[ i ][ j ] : 과일 종류 j개 中 i개를 훔치는 경우의 수 2. dp배열의 초기값을 채운다. 과일 i종 중 중 i개 훔치는 경우의 수 : 1 과일 1종 중 중 i개 훔치는 경우의 수 : 1 3. 나머지 원소들은 점화식을 통해 채운다. dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

📖 문제 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 💡 풀이 방식 • DP (0,0)부터 O 표시된 칸까지 가는 DP 한 번,O 표시된 칸부터 오른쪽 아래의 점 (N-1, M-1)까지 가는 DP 한 번해서총 2번의 DP를 진행하며 이동 경로의 수를 나타내는 2차원 배열 dp를 채웠다. 이 때 dp를 채우기 위한 점화식은 아래와 같다. dp[i][j] = dp[i-1][j] + dp[i][j-1];// 오른쪽과 아래쪽으로만 이동가능하다고 했으므로 (0,0)부터 오른쪽 아..

📖 문제 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net 💡 풀이 방식 • 조합 (DP) 파스칼 삼각형을 모두 왼쪽으로 밀었다고 생각하고 2차원 배열을 채운다. 맨 왼쪽 줄(= 0번째 열) 과 행=열인 칸은 값을 1로 채운다. 나머지 (i, j) 위치의 칸은 왼쪽 위 칸 (i-1, j-1)과 바로 윗 칸 (i-1,j)의 합으로 채운다. dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 점 (R,C)부터 길이가 W인 삼각형의 합을 구한다. 이 때 삼각형 모양으로 범위를 제한하기 위해 변수 tmp를 활용하며, 현재 행..

📖 문제 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 💡 풀이 방식 • 백트래킹 부분집합 (재귀) 을 활용해 팀을 나누고, 각 팀별로 능력치를 합하고 그 차이를 최솟값과 비교해 정답으로 출력한다. 💥 유의사항 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다. → 부분집합 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ..

📖 문제 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 💡 풀이 방식 • BFS 필요 자료구조 - 2차원 int형 배열 group : 0끼리 그룹화된 배열 정보 저장 - Map ⇒ 각각 다른 그룹으로 나눌 수 있다 (서로소 = 분리 집합) - BFS 통해 그룹 생성 시, 이미 만들어진 그룹에 속한 인덱스는 제외하고 탐색을 진행한다. - 벽(1)인 경우에만 본인 칸과 주변 상하좌우에 존재하는 0의 개수를 센다. (BFS 아니고 탐색 단 한 번) 💥 유의사항 N과 M이 각각 최대 1000이므..