BOJ9095 : 1, 2, 3 더하기 (Silver 3)

너무 오랜만에 DP 풀었더니 어케하는건지 완전 까먹었는데

인터넷에 치자마자 떠오름

 

DP == 점화식 세우기

 

그래서 DP 기본 문제는 코딩보다는 수학문제 푸는 것 같은 느낌이 든다..

 

처음에 이상한 짓하다가 인터넷의 힘을 빌려 힌트를 얻었고, 그 답은

 

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

 

 

예로, a5를 구한다고 해보면

a4 즉 4를 만드는 방법에 전부 +1 한 것 

+

a3 즉 3을 만드는 방법에 전부 +2 한 것

+ 

a2 즉 2를 만드는 방법에 전부 +3 한 것

 

이 바로 5를 만드는 방법의 전부이다.

(2) + 3

(3) + 2 

(4) + 1

 

괄호 안의 수를 나타내는 방법은 이미 앞에서 구해놨으니, 그 방법에다가 각각 3, 2, 1을 더하면 됨

 

 

#include <cstdio>
 
int dp[12] = { 0, 1, 2, 4, };
 
int main(void)
{
    int T, n, i;
    scanf("%d", &T);
 
    for (i = 4; i <= 12; i++)
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
 
    while (T--) {
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
 
    return 0;
}

 

 

원래 C++쓰는 나지만,,, 귀찮아서 기본 포맷은 인터넷 베껴워ㅓㅆ다

a3까지는 정의해주고 a4부터 점화식 활용해서 구해주면 끝

메모리나 시간 제한 신경쓸 필요 없는게, 주어지는 n이 11이하라고해서 미리 12까지 전부 디피를 돌려서 배열에 값을 저장해두고 필요한 값을 불러오면 된다

 

(만약 이 때 n이 커지고 시간제한이 걸리게 되면....? 으 골치아파)