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

9095. 1, 2, 3 더하기

문제 풀이

DP가 바로 이거구나! 알게 된 문제.

 

조금 고민해보다가... 생각해보니까 1을 만들 수 있는 연산, 2를 만들 수 있는 연산, 3을 만들 수 있는 연산을 가지고 계속 계속 다른 연산을 만들어가다보면 정답이 나오게 되는 것이었다!

 

만약에 4를 만든다고 하면...

input => 4

1 =>
1
arr[1] = 1

2 =>
1+1
2
arr[2] = 2

3 =>
1+1+1
1+2
2+1
3
arr[3] = 4

4 =>
4 = arr[1] + 3
4 = arr[2] + 2
4 = arr[3] + 1
이므로...

arr[4] = 1 + 2 + 4!

answer =>
7

 

코드로 구현해봤다.

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int tCnt;
    int dp[12] = { 0, };

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

    // 현재 값 =
    // dp[i-1] + 1
    // dp[i-2] + 2
    // dp[i-3] + 3

    // 따라서 현재 연산 횟 = dp[i-1] + dp[i-2] + dp[i-3]

    for (int i = 4; i <= 11; i++)
    {
        dp[i] += dp[i - 1];
        dp[i] += dp[i - 2];
        dp[i] += dp[i - 3];
    }

    cin >> tCnt;

    while (tCnt--)
    {
        int input;
        cin >> input;
        cout << dp[input] << '\n';
    }
}

 

정말 제대로 내가 생각해서 DP 문제를 풀어봐서 기분이 좋았다. 아직은 쉬운 DP 문제이지만... 그래도...

 

그리고 여담으로 #include<bits/stdc++.h> 헤더를 알게 되었다. 친구가 알려줬는데, 헤더를 하나하나 불러오지 않아도 이 친구가 필요한 헤더를 거의 다 가지고 있다고 한다.

 

비주얼 스튜디오에서는 헤더를 다운로드해주었어야 했는데, 백준은 그냥 제출해도 되는 것 같다.