아이디어 두 좌표 간에 최단 거리로 가는 방법은 (H, H) ~ (N, N) 범위 내에서만 움직이는 것이다. ex) (4, 4) ~ (8, 8) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? o o o o o ? ? ? ? o o o o o ? ? ? ? o o o o o ? ? ? ? o o o o o ? ? ? ? o o o o o 어차피 해당 범위 내에서만 움직인다면 (0, 0) ~ (4, 4) 랑 똑같으므로 이 점을 활용해서 배열의 크기를 |H - N| + 1 로 선언한다. 추가로 (H, H) ~ (N, N) 으로 가는 경로의 개수나 (N, N) ~ (H, H) 로 가는 경로의 개수나 동일하므로 (0,..
아이디어 조카에게 나눠줄 막대 과자의 길이를 X 라고 하면 나눠줄 수 있는 과자의 개수는 sum(L1 / X, L2 / X, ..., LN / X) 이다. 만약 위의 값이 조카의 수 M 보다 작으면 과자의 길이 X 가 너무 길다는 의미이므로 과자의 길이를 줄이고, M 보다 크면 과자의 길이 X 가 너무 작다는 의미이므로 과자의 길이를 늘려야 한다. 따라서 이분탐색을 통해 문제를 해결할 수 있고 막대 과자의 최대 길이를 출력해야 하므로 위의 값이 == M 이 되는 상황에서도 과자의 길이 X 를 늘려서 최대 길이를 구하면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; imp..
아이디어 A[i][j] 와 B[i][j] 가 다르다면 원소를 뒤집는 작업을 해야한다. (0, 0) 부터 순회하며 A[i][j] 와 B[i][j] 가 다르면 A 의 원소를 뒤집는 작업을 하되 (i, j) 를 뒤집을 때 이전에 뒤집어서 맞춰놓은 곳에는 영향을 미치면 안 되기 때문에 (i, j) 가 3 x 3 부분 행렬의 첫 번째가 되도록 한다. 즉 (i, j) ~ (i + 2, j + 2) 까지 뒤집어야 하는데 3 x 3 의 범위가 원본 행렬의 범위를 넘어가면 뒤집을 수 없다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer..
아이디어 dp[i][0] 을 i 번째 책상의 왼쪽에 앉은 학생을 선택했을 때 채점할 수 있는 최대 학생 수 dp[i][1] 을 i 번째 책상의 오른쪽에 앉은 학생을 선택했을 때 채점할 수 있는 최대 학생 수 라고 하면 해당 학생의 그레이드가 i - 1 번째 책상에 앉은 학생들의 그레이드와 같다면 dp[i][j] = dp[i][0] + 1 or dp[i][1] + 1 이 될 것이고 같은 그레이드가 없다면 dp[i][j] = 1 이 된다. 따라서 이를 고려해서 프로그램을 구현하면 원하는 답을 얻을 수 있다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.uti..
아이디어 보드의 크기는 최대 50 이기 때문에 배은 50 x 50 사이즈가 최대. 임의의 보드가 주어졌을 때 먹을 수 있는 사탕의 최대 개수를 계산하는 것은 2 * 50 * 50 이므로 5000번의 연산이 필요하다. 브루트포스 방식의 탐색에 필요한 연산 횟수는 50 x 50 x 5000 = 12,500,000 이므로 문제에서 요구하는 시간 제한인 1초를 통과하는 데는 무리가 없으므로 브루트포스 방식으로 문제를 해결하면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N; static char[][] board; sta..
아이디어 (a, b) 칸을 선택하면 해당 칸을 보다 좌, 상 단에 위치한 칸도 같이 뒤집히기 때문에 가장 우하단에 위치한 '뒷면' 동전부터 뒤집어가야 모든 동전을 정확히 앞면으로 만들 수 있다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRea..
아이디어 정수 n 에 대해서 n - 1 + 1, n - 2 + 2, n - 3 + 3 의 방법을 활용하면 1, 2, 3 의 합으로 나타내는 방법을 구할 수 있다. 다만 연속해서 같은 수를 사용하면 안 되기 때문에 n - 1 + 1 에 대해서 (n - 1) 은 (n - 3 + 2) 또는 (n - 4 + 3) 으로 구성이 되어야 한다. 따라서 아예 마지막에 j 를 더해서 i 을 만드는 경우의 수를 저장하는 배열을 만들어 dp[i][1] = dp[i - 1][2] + dp[i - 1][3] dp[i][2] = dp[i - 1][1] + dp[i - 1][3] dp[i][3] = dp[i - 1][1] + dp[i - 1][2] 와 같이 점화식을 만들어 계산을 한 뒤 dp[i][1] + dp[i][2] + dp..
아이디어 섬이 존재하는 좌표에서 dfs 를 수행해서 같은 섬(걸어갈 수 있는 좌표)을 탐색하면 1개의 섬의 땅을 모두 탐색할 수 있다. 이미 탐색한 섬은 다시 탐색하지 않도록 해서 모든 좌표에 대해 위의 방법을 적용하면 총 몇 개의 섬이 존재하는지 알 수 있다. 다만 이 문제에서 '걸어갈 수 있는 경로'는 상,하,좌,우 뿐만 아니라 대각선 방향으로 1칸씩 이동하는 것도 포함하므로 이 점을 생각하고 문제를 풀어야한다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[..