(실버 3)백준 16922: 로마숫자 만들기

시간 제한               메모리 제한                      제출                        정답                      맞힌 사람                  정답 비율

2 초

512 MB

7583

4180

3360

54.150%

문제

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.

하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.

실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.

로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

입력

첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.

 

---

내가 작성한 코드:

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int n;
int num[4] = {1, 5, 10, 50};
bool check[1001];
int result = 0;

void dfs(int idx, int number, int cnt)
{
    if (cnt == n)
    {
        if (check[number] == 0)
        {
            check[number] = 1;
            result++;
        }
        return;
    }

    for (int i = idx; i < 4; i++)
    {
        dfs(i, number + num[i], cnt + 1);
    }
}

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

    cin >> n;
    dfs(0, 0, 0);

    cout << result << '\n';

    return 0;
}

브루트포스와 백트래킹을 사용하여 해결한 문제이다.
문자가 아닌 숫자로 바꿔서 해결해보려 했고 2번의 시행착오가 있었다.
 
처음엔 중복 수를 set을 활용하여 잡아보려 했지만 시간초과가 나왔다.
그 다음 check라는 배열을 활용해 시도했으나 이 역시 시간초과가 나왔다. 
 
조금 더 생각을 해보니 xixx와 ixxx는 같은 수이기 때문에 중복으로 계산하는 것이 비효율적이라는 것을 알았고,
dfs에 idx변수를 추가하여 오름차순으로 정렬한 상태로 만든 뒤 기존 수에 더해서 해결했다.

---

이번에 Koala에 가입하여 다시 알고리즘 문제를 풀며 포스팅을 하게 되었다.
어려운 문제는 아니였으나 휴식기가 길어서인지 한번에 풀어내지는 못했다..
현재 왼쪽 어깨 탈구 이슈로 입원해있는데,
한손 코딩/포스팅은 썩 유쾌하지 않다..

시간 복잡도는 퇴원한 뒤 왼팔이 좀 자유로워지면 다시 작성해보겠다.