- 기타리스트 : 알고리즘은 같다. 단, 마지막에 만들 수 있는 숫자가 정해진 것이 아닌 최댓값을 구하는 문제이므로 DP[N]list[i-1]]처럼 특정 DP 공간을 검사하는 것이 아닌, DP[N][M]부터 M을 1씩 감소시키며 처음으로 0이 되지 않는 부분을 찾으면 된다. 숫자가 아니기 때문에 int 배열이 아닌 boolean 배열을 활용해도 무방할 것이다.
문제 이해
숫자가 N개 주어지며, 숫자 사이에 +나 -가 들어갈 수 있다.
또한 (N-1)개의 계산 결과값이 N번째 나온 수와 같아야 한다.
중간 계산 과정에서 음수는 나올 수 없고, 20을 넘을 수도 없다.
이런 조건에서 만들 수 있는 올바른 수식의 개수를 구하는 문제이다.
문제 풀이
현재 내가 확인할 수를 T라고 하자.
이전까지 계산한 결과값은 무조건 0이상 20 이하가 될 것이다.
따라서, arr[T-1][0] ~ arr[T-1][20]의 공간을 생성하자.
또한 arr[T-1][K]는 T-1번째 수까지의 수를 통해 만들 수 있는 K의 개수를 저장할 것이다.
만약 2 2 2이 입력되어 있다면, arr[3][6] = 1이 될 것이고(2+2+2 Case) arr[3][2] = 2가 될 것이다.(2-2+2, 2+2-2 Case)
내가 T번째 수의 계산 결과를 확인하고 싶다면 먼저 arr[T-1][0] ~ arr[T-1][20]의 모든 공간을 확인해야 한다.
그리고, 만약 해당 공간에 0이 저장되지 않았다면 T-1번재 수까지 K를 만들 수 있는 경우의 수가 존재한다는 것이다.
따라서, arr[T-1][S]가 0이 아닐 때, T번째 수로 만들 수 있는 수는 S+(T번째 수), 혹은 S - (T번째 수)가 될 것이다.
이를 이용해 arr[T][S+(T번째수)]와 arr[T][S-(T번째 수)] 값에 arr[T-1][S]를 더해주면 될 것이다.
코드
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N;
static int[] list;
static long[][] DP;
static void dp() {
DP[0][list[0]] = 1;
// 첫번째 수로 만들 수 있는 것은 list[0]이 유일하다.
for(int i = 1;i<N-1;i++) {
int prev = i-1;
for(int j =0;j<21;j++) {
if(DP[prev][j]==0) continue;
// 현재 i번째를 확인하고 있으며, 직전은 i-1 = prev 상황이다
// 만약 DP[prev][j] = 0이라면 prev까지의 숫자로
// j를 만들 수 없다는 의미이다.
// 이런 경우는 무시해준다.
for(int s:new int[] {j-list[i], j+list[i]}) {
// prev까지의 숫자로 j를 만들 수 있다.
// 즉, 현재 상황인 i번째 수를 통해 만들 수 있는 수는
// j - list[i], j+list[i] 2개이다.
if(s<0||s>20) continue; // 범위 벗어남
DP[i][s] += DP[prev][j];
// prev까지의 수에서 j를 만들었을 때 때 j에 i번째 수를
// 더하거나 빼주어 s를 만들 수 있다.
// 이 때의 경우의 수는 DP[prev][j]와 같을 것이다
// 따라서, DP[prev][j]를 더해준다.
}
}
}
}
public static void main(String[] args) throws IOException {
FastReader sc = new FastReader();
N = sc.nextInt();
list = new int[N];
DP = new long[N][21];
// DP[index][T] : index번째까지의 숫자로 T를 만들 수 있는 경우의 수
for(int i =0;i<N;i++) {
list[i] = sc.nextInt();
}
dp();
System.out.println(DP[N-2][list[N-1]]);
}
static class FastReader // 빠른 입력을 위한 클래스
}결과
-
4번째 줄 틀렸습니다 : 재귀함수를 통해 문제를 해결하려 했다. 하지만 재귀함수의 경우 현재의 상황을 미래의 상황을 통해 해결하는 방법이다. 계단 수처럼 마지막까지 연산이 수행되어야만 조건 충족 여부를 판단할 수 있는 문제가 아니라면 DP에서 재귀함수의 사용을 지양해야겠다.
-
3번째 줄 런타임 에러 : 괜히 마지막 수를 배열에 저장하지 않고 따로 값을 저장하여 계산 값을 비교하려 했다가 코드 구현 때 헷갈려 틀렸다. 마지막수까지 배열에 저장한 이후 배열의 범위를 설정하여 조금 더 직관적으로 문제를 풀자 해결되었다.
