[BaekJoon/백준] 9095번 C++

 

규칙이 없어서는 안될 문제라고 생각했는데, 규칙이 보이지가 않았다.

실버3에.. 정답률이 60인데 규칙이 없을리가 없다고 생각했다.

동적계획법으로 푸는 문제라고 확신했는데, 막상 규칙이 보이지 않았다.

 

 

이 문제가 이렇게 어렵게 푸는게 아닌 것 같은데.. 라고 생각하며  dfs 방식으로 풀어봤다.

#include <iostream>
using namespace std;

int N, T;
int ct;

void recur(int x) {
    
    
    if(x == 0) {
        ct++;
        return;
    } else if(x < 0)
        return;
    
    for(int i = 1; i <= 3; i++) {
        
        recur(x - i);
    }
}

int main() {
    
    ios::sync_with_stdio();
    cin.tie(NULL);
    
    cin >> T;
    
    while(T--) {
        ct = 0;
        
        cin >> N;
        recur(N);
        cout << ct << '\n';
    }
}

범위가 적다 보니 시간복잡도가 오래 걸리지 않아서, 문제가 풀리긴 풀린다.

 

 

근데 난이도상 dfs정도까지 나올 거 같지 않은 문제이고 동적계획법을 쓰는게 맞다고 생각되는데

규칙은 보이질 않아서 검색해봤다...

 

역시........... 나만 규칙을 못찾은 거였다 ..ㅜㅜ 동적계획법으로 푼 분들이 많았다. 간단한 규칙이 있었다. 나는찾지못했지만..

관련 자료는 아래 블로그를 참고하면 좋을 것 같다.

jyami.tistory.com/15