영벨롭 개발 일지

[백준 BOJ][C++]9095번 1, 2, 3 더하기 풀이: DP 본문

알고리즘 문제 풀이/BOJ

[백준 BOJ][C++]9095번 1, 2, 3 더하기 풀이: DP

영벨롭 2022. 2. 24. 16:28

https://www.acmicpc.net/problem/9095

 

9095번: 1, 2, 3 더하기

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

www.acmicpc.net

 

 이 문제는 Dynamic Programming 을 이용하여 해결할 수 있습니다. 

 

숫자 N 모든 경우  경우의 수  dp[N]
1 =1 1
2 =1+1
=2
2
3 =1+1+1
=1+2
=2+1
=3
4
4 =1+3
(3=1+1+1
   =1+2
   =2+1
   =3)
=2+2
(2=1+1
   =2)
=3+1
(1=1)
7
=dp[1]+dp[2]+dp[3]
5 =1+4
(4=1+1+1+1
   =1+1+2
   =1+2+1
   =2+1+1
   =2+2
   =1+3
   =3+1)
=2+3
(3=1+1+1
   =1+2
   =2+1
   =3)
=3+2
(2=1+1
   =2)
13
=dp[2]+dp[3]+dp[4]

 

 위 표를 보시면 숫자 N을 1, 2, 3의 합으로 나타내는 경우의 수는 N에서 각각 1, 2, 3을 뺀 값에 대한 수에 대한 경우의 수들의 합입니다. 

 

 dp[n]을 숫자 n을 1, 2, 3의 합으로 나타낸 경우의 수라고 하면,

 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] ,  (n>3) 이 됩니다. 

 

#include<iostream>

using namespace std;

int dp[11] = { 0, };

int main(void) {

	int t, n;

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

	cin >> t;

	while (t > 0) {

		cin >> n;

		if (dp[n] != 0) {
			cout << dp[n] << endl;
		}
		else {
			for (int i = 4; i <= n; i++) {
				dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
			}

			cout << dp[n] << endl;
		}

		t--;
	}


	return 0;
}
반응형