[개쉬운 풀이] 백준 15989 1, 2, 3 더하기 4 (8일차)

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

 

문제

 

생각

처음에는 이항계수 문제인 줄 알았다. 그러나 순서 상관 없이 오직 정수 1, 2, 3을 이용해서 모든 수를 만드는 문제이다. 

그래서 처음 DP로 접근하여 생각을 해보았다.

 

정수 / 3으로 3이 몇개 들어가는지 계산을 해보았고 이후 각 3의 개수에 따라 2가 들어가는 갯수만 세주면 나머지 1은 자동으로 빈자리를 채워준다. 이렇게 생각하니 DP까지도 생각할 필요 없이 단순 계산으로 풀 수 있었다.

 

즉, N을 3으로 나누고, 3을 몇개 쓸 것인지 for 문을 통해서 돌린다. 이후 3으로 사용하고 남은 나머지 값(=tmp)에 tmp/2 +1 하면 답이다.

->tmp/2 + 1에서 +1을 한 이유는 2를 아예 안쓰는 경우를 더한 것이다.

 

풀이

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 10001;

int process(int n){
    int answer = 0;

    for(int i = 0; i <= (n/3); i++){
        int tmp = n - (3*i);
        answer += tmp/2+1;
    }

    return answer;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        cout << process(n) << endl;
    }

    return 0;
}