백준 15988. 1, 2, 3 더하기 3

알고리즘 기초 문제 중 DP 연습 문제(401)

1, 2, 3 더하기 3

1, 2, 3 더하기 시리즈 문제 중 하나

순서대로 풀어봤다면 풀기 쉽다

1. 간단 설명

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제

DP 문제들을 풀다보니,

최대 최소값을 물어보는 문제는 보통 bruteforce, 방법의 개수를 물어보면 대부분 DP였다

2. 예시

• 1을 만드는 경우

  1 = 1 : 1로밖에 못만듬
  

• 2를 만드는 경우

  1+1
  2
  

• 3을 만드는 경우

  1+1+1
  1+2
  2+1
  3
  

• 4를 만드는 경우

  1+1+1+1
  1+1+2
  1+2+1
  2+1+1
  2+2
  1+3
  3+1
  

  이런식으로 n을 만들 수 있다

3. 알고리즘

dp[n][k]를 n을 만드는데, k(k=1,2,3)로 끝나는 경우의 수라고 하면

4를 만드는 경우를 예시로 들면 다음과 같다

dp[4][1] = 4가지 (1+1+1+1, 1+2+1, 2+1+1, 3+1)
dp[4][2] = 2가지 (1+1+2, 2+2)
dp[4][3] = 1가지 (1+3)

1+1+1+1은 1+1+1에 1을 더한 것이고, 1+2+1은 1+2에 1을 더한 것,

2+1+1은 2+1에 1을 더한것, 3+1은, 3에 1을 더한것이다

이를 식으로 정리하면

dp[4][1]은 dp[3][1], dp[3][2], dp[3][3]에 각각 1을 더한 것이므로

dp[4][1]은 dp[3][1] + dp[3][2] + dp[3][3]으로 정리할 수 있다

dp[4][2]는 1+1에 2를 더한것, 2+2에 2를 더한 것이므로

dp[4][2] = dp[2][1] + dp[2][2] + dp[2][3] 으로 정리할 수 있다

같은 방식으로 dp[4][3] = dp[1][1] + dp[1][2] + dp[1][3] 이다

즉 점화식을 정리해보면

dp[n][1] = dp[n-1][1] + dp[n-1][2] + dp[n-1][3]
dp[n][2] = dp[n-2][1] + dp[n-2][2] + dp[n-2][3]
dp[n][3] = dp[n-3][1] + dp[n-3][2] + dp[n-3][3]

으로 정리할 수 있다

4. 소스코드

#include <iostream>

#define MOD 1000000009

using namespace std;

int dp[1000001][4];

void init() {
	dp[1][1] = 1;
	dp[1][2] = 0;
	dp[1][3] = 0;

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

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

	for (int i = 4; i <= 1000000; i++) {
		dp[i][1] = ((dp[i - 1][1] + dp[i - 1][2]) % MOD + dp[i - 1][3]) % MOD;
		// 각 수를 합할 때, int형을 넘어가지 않도록 각 덧셈 연산마다 MOD 수행
		dp[i][2] = ((dp[i - 2][1] + dp[i - 2][2]) % MOD + dp[i - 2][3]) % MOD;
		dp[i][3] = ((dp[i - 3][1] + dp[i - 3][2]) % MOD + dp[i - 3][3]) % MOD;
	}
}

int main() {
	//freopen_s(new FILE*, "input.txt", "r", stdin);
	init();

	int T; cin >> T;
	while (T--) {
		int N;
		cin >> N;

		cout << (((dp[N][1] + dp[N][2]) % MOD) + dp[N][3]) % MOD << '\n';
	}

	/*
	정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하기

	dp[N][i]을 마지막 수가 i인, N을 만드는 방법의 수라고 할 때

	dp[N][1] =

	dp[1][1] = 1
	dp[1][2] = 0
	dp[1][3] = 0

	dp[2][1] = 1+1
	dp[2][2] = 2
	dp[2][3] = 0

	dp[3][1] = 1+1+1, 2+1
	dp[3][2] = 1+2
	dp[3][3] = 3

	dp[4][1] = 1+1+1+1, 1+2+1, 2+1+1, 3+1
	dp[4][2] = 1+1+2, 2+2
	dp[4][3] = 1+3

	dp[5][1] =
		4를 만드는데 1로 끝나는 수에 1을 더하기(dp[4][1]) +
		4를 만드는데 2로 끝나는 수에 1을 더하기(dp[4][2]) +
		4를 만드는데 3으로 끝나는 수에 1을 더하기(dp[4][3])의 개수의 합
	dp[5][2] = dp[3][1] + dp[3][2] + dp[3][3]
	dp[5][3] = dp[2][1] + dp[2][2] + dp[2][3]

	...

	dp[N][1] = dp[N-1][1] + dp[N-1][2] + dp[N-1][3]
	dp[N][2] = dp[N-2][1] + dp[N-2][2] + dp[N-2][3]
	dp[N][3] = dp[N-3][1] + dp[N-3][2] + dp[N-3][3]
	*/

	return 0;
}

5. 개선방안

dp를 2차원 배열로 놓지 않고, 1차원으로도 충분히 가능한 문제였다

dp[n]를 n을 만드는 방법의 수라고 하면

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]으로도 충분히 해결 가능

#include <iostream>

#define MOD 1000000009

using namespace std;

int dp[1000001]; // N을 만드는 방법의 수

void init() {
	dp[1] = 1; // 1을 만드는 방법의 수 1개 (1)
	dp[2] = 2; // 2를 만드는 방법의 수 2개 (1+1, 2)
	dp[3] = 4; // 3을 만드는 방법의 수 3개 (1+1+1, 1+2, 2+1, 3)

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

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	init();

	int T; cin >> T;
	while (T--) {
		int N;
		cin >> N;

		cout << dp[N] << '\n';
	}

	return 0;
}