백준, BOJ, 16922번, 로마 숫자 만들기 C++ [CPP] ★★★★

이 문제는 쉬웠지만 시간초과가 나는 이유를 간과했다.

분명 순서가 쓸모 없음에도.. 나는 순서를 고려하여 세지 않아도 되는

경우의 수까지 고려해서 시간 초과가 난 것이다.

그냥 무지성 백트래킹을 박아버렸다.

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

set<int> counts;

vector<int> vec = {1,5,10,50};

// 최대 카운트, 현재 카운트, 현재 문자, 결과합
void func(int maxi, int cnt, int idx, int res){
    if(cnt >= maxi){
        counts.insert(res);
        return;
    }
    
    //문자의 순서는 상관없으므로 각 문자의 개수만 고려한다.
    //1번문자 a개 2번문자 b개 등...
    for(int i=idx; i<4; i++){
        func(maxi, cnt+1, i, res + vec[i]);
    }
    

}


int main(){
    int n;
    cin >> n;
    
    func(n, 0, 0, 0);
    long long ans = counts.size();
    cout << ans << '\n';
    
    
    
    return 0;
}