[백준] 9095_1, 2, 3 더하기 C++

11 Oct 2023 in Study on Coding Test

기초 DP 문제

정답제출코드

#include <iostream>

using namespace std;

int DP[11];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int T;
    cin >> T;
    
    DP[1] = 1;
    DP[2] = 2;
    DP[3] = 4;
    
    for (int i = 4; i <= 10; ++i)
        DP[i] = DP[i-3] + DP[i-2] + DP[i-1];
    
    for (int tc = 1; tc <= T; ++tc)
    {
        int N;
        cin >> N;
        
        cout << DP[N] << '\n';
    }
    
    return 0;
}

1부터 차근차근 구해보자.

1의 경우는 1이고, 2의 경우는 1+1, 2로 2가지 경우이다.

그리고 3의 경우는 1+1+1, 1+2, 2+1, 3 으로 4가지 경우이다.

그리고 문제에 나와있듯이 4의 경우는

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

위와 같이 7가지 경우이다.

그리고 5의 경우는

4+1
3+2
2+3

으로 나타낼 수 있을 것이다.

이를 1, 2, 3의 합으로 확대(?)하면

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

1+1+1+2
2+1+2
1+2+2

1+1+3
2+3

으로 확대가 가능하며, 이는 총 12가지이다.

보면 중복되는 경우 없이 깔끔하게 처리가 된다!

여기서 점화식을 세울 수 있다.

F(N)이 N을 1, 2, 3 의 합으로 나타낼 수 있는 경우의 수라면

F(N) = F(N-1) + F(N-2) + F(N-3) (N >= 4)

로 처리해줄 수 있다!

이를 for문으로 나타내면 DP를 이렇게 깔끔하게 처리가 가능하다.

for (int i = 4; i <= 10; ++i)
	DP[i] = DP[i-3] + DP[i-2] + DP[i-1];

Top-Down방식.

사실 n의 범위가 10 이하의 양의 정수이기 때문에

재귀함수를 사용하는 Top-Down 방식도 사용할 수 있다.

int Solve(int n)
{
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	if (n == 3)
		return 3;
	
	return Solve(n-1) + Solve(n-2) + Solve(n-3);
}

위 함수를 사용하면 될 것이다.

다만, 재귀호출을 하는데 시간이 오래걸릴 수 있으니

DP를 0으로 초기화 해준다음

if (DP[n] != 0)
	return DP[n];

을 해주는 것도 참고하자.