아이디어 어떤 무게를 측정할 수 있는 상태에서 X g 짜리 구슬을 하나 추가한다면 '측정할 수 있는 무게 + X, |측정할 수 있는 무게 - X|' 이 2가지 무게 또한 측정할 수 있게 된다. dp[i][j] 를 i번째 구슬까지 추가했을 때 j 무게를 측정할 수 있는지 여부라고 정의한다면 dp[i][j] = dp[i - 1][j] 또는 dp[i - 1][ | j - j번째 구슬 무게 | ] 또는 dp[i - 1][j + j번째 구슬 무게] 가 된다. 측정할 수 있는 무게의 최대치는 모든 구슬 무게의 합이므로 이 값을 j 의 최대 범위로 설정해서 dp 배열을 만들면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java..

아이디어 시작점에서 임의의 i, j 까지 상승 비행 했을 때의 점수 + 임의의 i, j 에서 끝점까지 하강 비행 했을 때의 점수를 계산하고 모든 i, j 를 탐색하면서 그 값이 가장 큰 것을 출력하면 된다. 임의의 i, j 에서 끝점까지 하강 비행했을 때의 점수는 역으로 생각하면 끝점에서 임의의 i, j 까지 상승 비행 했을 때의 점수가 되므로 이를 활용해 문제를 해결하면 된다. ascending[i][j] = Math.max(ascending[i + 1][j], ascending[i][j - 1]) + score[i][j] descending[i][j] = Math.max(descending[i + 1][j], descending[i][j + 1]) + score[i][j] dp[i][j] = asce..

아이디어 지울 수 있는 문자열 중에 점수가 큰 것부터 지워나가면 되지 않을까 생각했지만 이런 그리디 방식의 탐색은 bab 2 bab 3 a 2 와 같은 사례에서는 통하지 않는다. 따라서 문자열 S 를 앞에서부터 탐색해가면서 지울 수 있는 문자열이 등장했을 때 이를 통으로 지우는 것 vs 단순히 문자 하나를 지우는 것 중 어떤 방법이 더 점수를 높게 가져갈 수 있는지를 확인하는 방식을 사용해야 한다. dp[i] 를 문자열 S 에 대해 i 번째 문자까지 탐색했을 때 최대 점수 라고 정의한다면 dp[i] = Math.max(dp[i - 1] + 1, dp[i - 지울 수 있는 문자열의 길이] + 지울 수 있는 문자열의 점수) 가 된다. 풀이코드 import java.io.BufferedReader; impor..

아이디어 어떤 수열을 팰린드롬으로 만들기 위해 기본적으로 생각해볼 수 있는 과정은 다음과 같다. 1. 시작 숫자와 끝 숫자가 다른 경우 시작 숫자를 끝에 추가 후 시작 index + 1 or 끝 숫자를 시작에 추가 후 끝 index - 1 2. 시작 숫자와 끝 숫자가 같은 경우 시작 index + 1, 끝 index - 1 로 이동 문제는 1번 케이스에서 전자와 후자 중 어떤 방식을 취하는 것이 최소가 되는 방식인 지를 알아내야 하는 것인데 이 때 dp 를 활용하면 된다. dp[i][j] 에서 i 를 시작 index, j 를 끝 index 로 바라보면 numbers[i] != numbser[j] 일 때 dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1 numbe..

아이디어 결국 임의의 i 번째 작업을 가장 빨리 완료할 수 있는 시간은 '선행 작업 중 가장 늦게 끝나는 작업 + i 번째 작업의 소요 시간' 이다. 따라서 dp[i] 를 i 번째 작업을 가장 빨리 완수할 수 있는 시간이라고 정의한다면 dp[i] = max(dp[선행1], dp[선행2],..) + i 번째 작업의 소요 시간 이라고 할 수 있다. 그리고 문제에서 요구하는 것은 모든 작업을 완료하기 위한 최소 시간이므로 모든 작업들에 대해 dp[i] 를 구한 뒤 그 중 가장 최대값을 뽑아내면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Str..

아이디어 dp[i] 를 수도관 길이의 합이 i 가 되게 만들 때 가능한 최대 수도관 용량으로 정의를 한다. 입력 받는 수도관 순서대로 1 ~ D 까지의 길이에 대해 현재 입력 받은 수도관을 덧붙여 i 를 만드는 것과 그렇지 않고 이전 값을 유지하는 경우 중 더 큰 값을 dp[i] 로 갱신해준다. 이 때 입력 받은 수도관을 덧붙여 i 를 만들 경우 dp[i - L] 과 현재 입력 받은 수도관의 용량인 C 중 더 작은 값이 해당 케이스의 수도관 용량이 된다. dp[i] = Math.max(dp[i], Math.min(dp[i - L], C)) 다만 이 때 특정 수도관에 대해 1 ~ D 를 정방향으로 탐색하게 되면 dp[L] 에 대해 입력 받은 수도관을 사용하는 것으로 결정을 했는데 dp[2L] 에 대해서도 ..

아이디어 dp[i][j] 를 1 ~ j 까지 숫자 중 i 개를 문제에서 요구하는 규칙에 따라 뽑을 때 경우의 수라고 정의 dp[i][j] 는 1 ~ j / 2 까지 i - 1 개를 뽑고 여기에 j 를 추가하는 케이스들 + 1 ~ j-1 까지 i 개를 뽑은 케이스들의 합이된다. dp[i][j] = dp[i - 1][j / 2] + dp[i][j - 1] 풀이코드 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..

아이디어 (()[[]])([]) 를 문제에서 제시한 1 ~ 5에 따라 하나씩 풀어가보면 = (2+[3])+(3) = (2+3*3)+(3) = 2*2+2*3*3+2*3 = 28 가 되는 것을 알 수 있다. : 1 ( : 2 (( : 2 * 2 (() : 2, answer = 2 * 2 (()[ : 2 * 3 (()[[ : 2 * 3 * 3 (()[[] : 2 * 3, answer = 2 * 2 + 2 * 3 * 3 (()[[]] : 2 (()[[]]) : 1 (()[[]])( : 2 (()[[]])([ : 2 * 3 (()[[]])([] : 2, answer = 2 * 2 + 2 * 3 * 3 + 2 * 3 (()[[]])([]) : 1 결국 실제로 값이 만들어지는 시점은 (), [] 와 같이 쌍을 이루는..