개요

백준15988(1,2,3 더하기 3)

문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

접근 방식

1. dp배열을 선언했다. dp[i]는 숫자 i 를 만들 수 있는 경우의 수이다.

2. dp[1]=1;
   dp[2]=2;
   //dp [1] + dp[2]+ 1(3도 되므로)
   dp[3]=4;
   //dp[1]+dp[2]+dp[3]
   dp[4]=7;

   dp[4]까지 구하고보니 그냥 이전 값들을 다 더한 값이여서
   아주 단순하게 일단 모든 dp를 더하는 식으로 풀어서 제출해봤다.
   역시나 틀렸다.

3. 좀 생각해보니 숫자를 덧셈으로 나열할 때 구조가 있었다.
   5를 예시로 들면
   1+4
   2+3
   3+2
   4+1
   여기서 덧셈의 앞 부분은 1부터 순차적으로 증가하고, 뒷부분은 5- 앞부분이다.

4. 여기서 많이 생각했던 부분은 중복처리 여부였다.
   예를들어 2+3을 dp[2]+dp[3]으로 처리하게되면
   dp[2]에는 1+1도 포함되어있어 결국 dp[1]+dp[4]의 경우와 겹치는 부분이 생긴다.
   고민을 하다가 단순한 생각을 떠올렸다.
   앞부분은 1부터 증가시키면서 고정시키는 것이다.
   위의 예시처럼 2+3이라면 dp[2]+dp[3]이 아닌 2+dp[3]이다. 2는 고정이고 경우의 수는 dp[3]이다.
   이런 식으로 앞부분을 고정시켜버리면 쌍이 중복될 수가 없다.
   앞이 1일때 경우와 앞이 2일때 경우는 이미 앞 숫자부터 중복이 아니지 때문

5. 따라서 각 케이스의 경우의 수는 뒷부분에 의존한다.
   1+4 , dp[4] 가지 경우의 수
   2+3 , dp[3]가지 경우의 수
   3+2 , dp[2]가지 경우의 수
   4+1 , dp[1]가지 경우의 수

   일반화를 해보자면 숫자 N을 만들 때,
   1+ (N-1) = dp[N-1]가지 경우의 수
   2+ (N-2) = dp[N-1]가지 경우의 수
   3+ (N-3) = dp[N-1]가지 경우의 수
   4+ (N-4) = dp[N-1]가지 경우의 수

   이런식이다.
   따라서 계산해보니 결국 dp[i]를 구할 때, dp[0]부터 dp[i-1]까지 전부 더하는 식이다.
   따라서 왜 위 방식이 틀렸나 곰곰히 생각해봤는 데, 바보다.
   1부터 3으로만 나타내기인데, 덧셈의 앞부분에 4가 들어갈 순 없다.

6. 따라서 1+ (N-1) , 2 + (N-2) , 3+(N-3) 이렇게 세가지 값만 보면된다.

전체 코드

#include<iostream>

using namespace std;

//index숫자를 만드는 경우의 수
long long dp[1'000'002];
int N,tmpNum;

int main(){
    dp[1]=1;
    dp[2]=2;
    //dp [1] + dp[2]+ 1(3도 되므로)
    dp[3]=4;
    //dp[1]+dp[2]+dp[3]
    dp[4]=7;

    /*
    dp[5]= 1+4의꼴 (dp[4]), 2+3의 꼴 (dp[3]),3 +2 꼴 (dp[2]) 13
    dp[6]=1+5 (dp[5]) +2+4 (dp[4]) +3+3 (dp[3])  = 24
    dp[7] =1+6 (dp[6]), 2+5(dp[5]), 3+4(dp[4]) = 44
    
    */
   cin>>N;

    for(int i=5;i<=1'000'001;i++ ){
        //dp[i-1]은 dp[i-1]까지의 모든 합 
        dp[i] = (dp[i-1]%1'000'000'009 + dp[i-2]%1'000'000'009+dp[i-3]%1'000'000'009)%1'000'000'009;
    }

    for(int i=0;i<N;i++){
        cin>>tmpNum;
        cout<<dp[tmpNum]<<"\n";
    }
}

문풀후생

dp값 long long으로 해줘야한다. int면 범위 넘어간다아