[15990번] 1, 2, 3 더하기 5 ( 메모이제이션 )

---

---

✅ 점화식

DP는 구할 수 있는 모든 경우의 수를 나열해보면서 규칙을 찾는 게 가장 좋다.

---

✅ 시간 초과

테스트 케이스는 맞게 나오는데, 시간 초과가 나네?
아...! n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력하라고 되어있었군!

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

public class Main {
	static int[][] dp;
	static int MOD = 1000000009;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine());


		for (int t = 0; t < test; t++) {
			
			int n = Integer.parseInt(br.readLine());
			dp = new int[n + 1][4];

			if (n == 1 || n == 2) {
				System.out.println(0);
				return;
			}

			for (int i = 3; i <= n; i++) {
				if (i == 3) {
					dp[i][1] = 1;
					dp[i][2] = 1;
					continue;
				}
				if (i == 4) {
					dp[i][1] = 2;
					dp[i][3] = 1;
					continue;
				}
				if (i == 5) {
					dp[i][1] = 1;
					dp[i][2] = 2;
					dp[i][3] = 1;
					continue;
				}

				dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
				dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
				dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
			}
			int result = (dp[n][1] + dp[n][2] + dp[n][3]) % MOD;
			System.out.println(result);

		}
	}
}

이 코드의 문제가 뭘까

테스트 케이스 마다 dp배열을 계산하게 된다.
만약에 테스트 케이스가 1000000 이고 테스트 케이스 마다 n = 100000 이면 시간 초과가 난다.

O(test * (1 + n))

메모이제이션을 활용해야 할 것 같다!

---

✅ 코드

1은 1로 2은 2로 3은 3으로 나타낼 수 있었는데, 고려를 못해줘서 틀렸고
dp배열을 long으로 선언해주어야 했다.

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

public class Main {
	static long[][] dp = new long[100001][4];
	static int MOD = 1000000009;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine());

		dp[1][1] = 1;
		dp[2][2] = 1;
		dp[3][1] = 1;
		dp[3][2] = 1;
		dp[3][3] = 1;

		for (int i = 4; i <= 100000; i++) {
			dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
			dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
			dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
		}

		for (int t = 0; t < test; t++) {
			int n = Integer.parseInt(br.readLine());
			System.out.println((dp[n][1] + dp[n][2] + dp[n][3]) % MOD);
		}
	}
}

---