Baekjoon 9095번 1, 2, 3 더하기

문제

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

걸린 시간

01 : 41 : 02

풀이

Python3

def ways(n, s, v):
    count = 0
    s += v

    if s == n:
        return 1
    elif s > n:
        return 0
    else:
        count += ways(n, s, 1) + ways(n, s, 2) + ways(n, s, 3)

    return count

if __name__ == "__main__":
    T = int(input())    

    result = []

    for _ in range(0, T):
        n = int(input())
        result.append(ways(n, 0, 0))

    for i in result:
        print(i)

이렇게 오래 걸릴 문제가 아니엇다.

순환을 이용하면 간단히 해결될 것을 DFS 문제로 보고 한참 동안 삽질을 했다.

다른 풀이

C++

#include <stdio.h>
#include <iostream>
#include <string.h> // memset
using namespace std;

int N;
int cache[10]; // 인덱스 : 누적값, 값 : 방법의 수

int solve(int n){
    // 기저 사례
    if(n == N)
        return 1;
    if(n > N)
        return 0;
    // 메모이제이션
    int &ret = cache[n];
    if(ret != -1)
        return ret;
    // 재귀 호출
    return ret = solve(n+1) + solve(n+2) + solve(n+3);
}

int main(){
    int tc;
    scanf("%d", &tc);
    while(tc--){
        scanf("%d", &N);
        memset(cache, -1, sizeof(cache));
        printf("%d\n", solve(0));
    }
    return 0;
}

메모이제이션을 적용한 동적 계획법 풀이이다.