[BOJ] 9095 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

dp

 

---------------------------------------------------풀이----------------------------------------------------

 

1,2,3이 기본 값이므로 method[]에 각 숫자를 만드는 방법의 수를 미리 저장한다.

1 = 1

2 = 1+1

   = 2

3 = 1+1+1

   = 1+2

   = 2+1

   = 3

위와 같이 method[1] = 1, method[2] = 2, method[3] = 4이다.

solution()함수에서는 n값을 구하는 방법을 리턴한다.

만약 이미 method[n]이 존재한다면(0보다 크다면) 그 값을 리턴하고,

아니라면 이 값을 구해서 method[n]에 저장한 뒤 리턴한다.

n을 만드는 방법은 다음과 같다.

n = 1+(n-1)

   = 2+(n-2)

   = 3+(n-3)

따라서 method[n] = solution(n-1)+solution(n-2)+solution(n-3)이다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

// 각 숫자를 1,2,3을 이용해 나타내는 경우의 수
int method[12] = {0, };

int solution(int n){
    // 이미 구해진 값이면 바로 리턴
    if(method[n] > 0){
        return method[n];
    }
    int ans = 0;
    for(int i = 1; i <= 3; i++){
        // n = i + (n-1)일 경우!
        ans += solution(n-i);
    }
    return method[n] = ans;
}

int main(void){
    FASTIO;
    int T;
    cin >> T;
    method[1] = 1;  // 1 = 1
    method[2] = 2;  // 2 = 1 + 1
    method[3] = 4;  // 3 = 1 + 1 + 1 = 1 + 2 = 2 + 1 = 3
    for(int t = 0; t < T; t++){
        int n;
        cin >> n;
        cout << solution(n) << "\n";
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

단순한 dp문제.