(C++) - 백준(BOJ) 15989번 : 1, 2, 3 더하기 4

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

15989번: 1, 2, 3 더하기 4

dp문제였습니다.

 

풀이방법

 특정한 규칙을 수학적으로 찾으면 답을 도출할 수 있습니다.

1111은 22로 교체될 수 있습니다.

222는 33으로 교체될 수 있습니다.

적절히 규칙을 찾으면 점화식을 구할 수 있습니다.

Code(Top down, 주석은 bottom up)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int t, n;
ll d[10001];

ll dp(ll num){
    if(num <= 2) return num;

    ll &ret = d[num];
    if(ret != -1) return ret;
    ret = 0;

    ll a = num;
    if(a % 2 == 0) a /= 2;
    else a = a / 2 - 1;
    a /= 3;
    ret = dp(num - 1) + a + 1;
    return ret;
}

int main(){
    cin >> t;
    memset(d,-1,sizeof(d));
    // for(int i = 3; i <= 10000; i++){
    //     ll a = i;
    //     if(a % 2 == 0) a /=2;
    //     else a /= 2, a--;
    //     a /= 3;
    //     d[i] = d[i-1] + a + 1;
    // }
    
    while(t--){
        cin >> n;
        cout << dp(n) << '\n';
    }
}