[백준] 9095 번 : 1,2,3 더하기 / C++

[문제]

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

 

 

 

문제 :

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력 : 

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

출력 :

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

 

[코드 풀이]

[성공한 코딩]

DP를 이용해서 문제를 풀었는데, 1부터 4까지 1,2,3의 덧셈으로 만들 수 있는 조합의 수를 확인해보다가 규칙이 있음을 깨닫게 되었다. 

1 : 1 개 , 2 : 2개, 3 : 4개, 4 : 7개
이전 3개의 수의 조합 개수를 다 더하면 현재 숫자의 조합의 개수가 나온다는 것을 알 수 있다.

수학적 귀납법을 이용하면 되겠지만, 그 규칙을 공식화하지는 않았다. 귀찮다. 그냥 규칙 찾았으니 바로 코딩해보자.

#include <iostream>
#include <array>
#include <vector>
#include <cstring>

//백준 문제 9095번 1,2,3 더하기 문제

int dp[1000];

int func(int inp) {
    if (dp[inp] != -1) {
        return dp[inp];
    }
    if (inp <= 2) {
        dp[inp] = 1;
    }
    else if (inp == 3) {
        dp[inp] = 2;
    }
    else {
        dp[inp] = func(inp-1) + func(inp-2) + func(inp-3);
    }
    return dp[inp];
}

int main() {
    int test_number = 0;
    std::cin >> test_number;
    int input = 0;
    memset(dp,-1,1000*sizeof(int));
    
    //std::cout << func(test_number);
    for (int i = 0; i < test_number; i++) {
        std::cin >> input;
        std::cout << func(input+1) <<'\n';
    }
    return 0;
}

DP를 이용해서 최적화하여 풀게 됐다. 메모이제이션으로 이전 값들을 기억하고, 나중에 계산 시 찾으면 된다. func 부분에서 규칙을 코딩하여 풀게 됐다.

 

[후기 및 배운 점]

DP 공부를 하려고 했는데 그냥 피보나치에서 항 하나 추가한 느낌이다. 흠.. 처음에는 개수를 구하는데 공식이 있지 않을까 했는데 그냥 노가다로 개수만 찾고, 규칙이 있음을 깨닫고 바로 적용해버렸다. 수학 공부 좀 더 해야겠다.

 

DP의 메모이제이션만 이용한 느낌이라 좀 더 DP를 공부해볼 겸 다른 문제들도 풀어봐야겠다.