cpp) 백준 9095: 1, 2, 3 더하기

Problem

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

9095번: 1, 2, 3 더하기

 

 

Solution

#include<iostream>
#include<string.h>

using namespace std;

int t;          // 테스트케이스 수
int n;          // 정수 n
int cache[12];  // 방법의 수 저장

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    memset(cache,0,sizeof(int));  // 메모리 초기화
    cache[1]=1;
    cache[2]=2;
    cache[3]=4;

    cin >> t;
    for(int i=0;i<t;i++){
        cin >> n;
        for(int i=4;i<=n;i++){
            cache[i]=cache[i-1]+cache[i-2]+cache[i-3];
        }
        cout << cache[n] << '\n';
    }


  
    return 0;
}

이 문제는 dp 알고리즘으로 풀수 있다. 각각의 경우의 수에 대한 예상 결과값을 확인하고 규칙이 발견되면 위와 같이 점화식을 세울 수 있다.

 

 

Reference

https://sanghyu.tistory.com/108

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