[5557번] ( DP, 대부분 1-2차원 배열로, 3번 생각하는 문제 )

✅ 점화식

점화식을 세우는 게 가장 중요한데, 내가 세운 점화식은 그 전 dp의 값에서 +1을 해주는 거였다.
근데, 한 번 더 깊게 생각해서 풀어야 하는 문제였다.
그래서 골드구나!

일단 DP는 1차원 배열 아니면 2차원 배열인 걸 염두에 두고 1차원 안되면 2차원으로 두는 게 좋을 것 같다.

여기서

dp[i][plus] += dp[i - 1][j];

plus=11 이라면 11이라는 수가 될 수 있는 연산 경우의 수이다.
배열을 앞에서부터 탐색하니까 먼저 앞에서 11을 만들 수 있는 경우가 있어서 1이 된다.
그 다음 번째에서 또 11이 될 수 있을 때는 그 1이라는 값에서 1을 더한다.
근데, 중요한 건 1의 값을 더할 때 단순히 1의 값을 더하는 것이 아닌 앞에서 될 수 있는 경우의 수가 2라면 +1이 아닌 +2를 해줘야 한다는 것!

✅ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int[] A;
	static long[][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		A = new int[N];
		dp = new long[N][21];

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}

		dp[0][A[0]] = 1;


		for (int i = 1; i <= N - 2; i++) {
			for (int j = 0; j <= 20; j++) {
				if (dp[i - 1][j] != 0) {
					int plus = j + A[i];
					int minus = j - A[i];
					if (plus >= 0 && plus <= 20) dp[i][plus] += dp[i - 1][j];
					System.out.println(j);
					System.out.println(dp[i - 1][j]);
					if (minus >= 0 && minus <= 20) dp[i][minus] += dp[i - 1][j];
				}
			}
		}

		for (int i = 0; i < N - 1; i++) {
			for (int j = 0; j <= 20; j++) {
				System.out.print(dp[i][j] + " ");
			}
			System.out.println();
		}

		System.out.println(dp[N - 2][A[N - 1]]);

	}

}