아이디어 배추흰지렁이 1마리로 인접한 배추들을 모두 커버할 수 있다. 따라서 (0, 0) ~ (N - 1, M - 1) 중 배추가 심어진 위치에서 dfs 를 수행해서 인접한 배추들을 탐색하도록 해서 dfs 가 총 몇 번 수행되는지를 세면 그것이 곧 최소 배추흰지렁이 마리 수가 된다. 이때 이미 dfs 를 수행해서 한 번 탐색한 위치에서는 또 dfs 를 수행하지 않도록 주의해야 한다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int M; static int N; st..

아이디어 dp[i] 를 i 번째 숫자를 마지막으로 하는 최대부분배열의 합이라고 정의한다면 다음과 같은 점화식을 세울 수 있다. dp[i] = Math.max(dp[i - 1], 0) + numbers[i] i - 1 번째 숫자를 마지막으로 하는 최대부분배열의 합이 음수라면 i 번째 숫자만으로 이루어진 배열이 i 번째 숫자를 마지막으로 하는 최대부분배열이 되기 때문이다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args)..

아이디어 상자를 최소한으로 쓰기 위해서는 용량이 큰 상자부터 꽉꽉 채워담아야 한다. 만약 사용한 상자를 모두 다 채워야 한다고 하면 이야기가 다르겠지만 문제에서 상자를 다 채우지 않아도 된다고 했으므로 그리디한 방식으로 문제를 해결하면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new B..

아이디어 시간 제한이 0.5 초이고 B 는 최대 2,147,483,647 이기 때문에 직접 모든 반복 연산을 수행하는 것은 시간 초과가 나게 된다. 지수법칙과 모듈러 연산을 이용해서 시간 초과는 물론 타입에 따른 오버플로우를 방지하는 방법을 사용하면 문제를 해결할 수 있다. 지수법칙에 의하면 a ^ b = a ^ (b / 2) * a ^ (b / 2) 이고 모듈러 연산에 의하면 (A * B) % C = ((A % C) * (B % C)) % C 이므로 이를 통해 굳이 b번 반복 연산을 수행하지 않아도 원하는 값을 얻을 수 있게 되는 것이다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRe..

아이디어 점화식 문제는 t(n) 의 값을 얻기 위해서 이전 값들인 t(0) ~ t(n - 1) 을 활용하는 문제이다. t(i) 는 t(i + 1) ~ t(n) 까지의 계산에 모두 필요한데 매번 t(i) 를 계산하면 비효율적이므로 한 번 계산된 t(i) 값은 배열에 저장해뒀다가 다음에 필요할 경우 꺼내서 이를 사용하는 'DP' 방식을 활용해서 문제를 풀면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br..

아이디어 첫 번째 수를 N, 두 번째 수를 X 라고 할 때 수열은 다음과 같다 N, X, N - X, 2X - N, 2N - 3X, ... 수열의 길이가 최대가 되기 위해서는 N - X >= 0, 2X - N >= 0, 2N - 3X >= 0, ... 의 조건들을 최대한 많이 만족시킬 수 있는 X 를 선택해야 한다. 일단 1번째 조건에 의해서 N >= X 가 되는 범위에서 X 를 선택해야 하는 것을 알 수 있는데 이 때 N 을 선택하면 N, N, 0, N 으로 길이가 4인 수열을 얻을 수 있다. 모든 입력값 N 에 대해서 최소 4개는 보장이 된다는 뜻이므로 2X - N >= 0 인 범위에 대해서 그 후 조건들을 얼마나 만족시킬 수 있는지를 확인해서 수열의 길이가 최대가 되는 케이스를 출력하면 된다. 풀이..

아이디어 a1 + ... + an = S 라고 할 때 이를 두 개의 막대로 자르면 K, S - K 인 막대가 되며 이 때의 비용은 K(S-K) 이다. K 를 어떻게 결정할 것인지의 문제이므로 이를 K 에 대한 2차 함수라고 생각하면 계수가 음수이므로 K 가 최소 또는 최대가 될 때 비용 또한 최소가 된다. 이는 곧 두 개의 막대로 자를 때 최소한의 비용을 사용하는 방법은 a1 ~ an 중 가장 작은 막대의 길이만큼 자르는 것이라는 의미이다.(더 작게 자르면 현우가 원하는 막대를 모두 만들 수 없음) 따라서 a1 ~ an 이 오름차순 정렬됐다고 가정할 때 a1 * (a2 + ... + an) 이 막대를 둘로 자르는 최소 비용이 되는 것이다. 한 번 막대를 잘라서 a1 을 얻었다면 (a2 + ... + an..

아이디어 이 문제는 결국 0 으로 통일할 것인가? 1로 통일할 것인가? 를 결정하는 문제다. 0 으로 통일하는 과정은 연속된 1로 이루어진 구역들을 각각 뒤집는 것이 최소 횟수이고 1 로 통일하는 과정은 연속된 0으로 이루어진 구역들을 각각 뒤집는 것이 최소 횟수이므로 입력으로 들어오는 문자열에서 연속된 0 으로 이루어진 구역의 갯수와 연속된 1로 이루어진 구역의 갯수를 세서 더 작은 값을 출력하면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOExc..