[C++] 백준 16922번 - 로마 숫자 만들기 (중복 조합)

문제 링크 : www.acmicpc.net/problem/16922

16922번: 로마 숫자 만들기

 

문제

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

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

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

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

입력

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

출력

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

 

 

 

---

 

접근 방법

 

완전탐색 문제라 모든 경우의 수에 대해 DFS 로 풀었는데 시간 초과가 떴다.

문제의 조건에서 순서를 상관하지 않으므로 IIX = XII 이다. 이는 중복 조합으로 해결할 수 있다.

 

중복조합은 서로 다른 n개 중 k 개를 뽑는 경우인데, 여기서는 서로 다른 4개(I,V,X,L) 개 중 중복을 허용하고 순서 상관 없이 N개를 뽑는것이다.

 

 

DFS() 안의 반복문을 보자.

시작 값을 변화시킴으로써 중복 조합을 구현할 수 있다. i의 변화 값은 다음과 같다. (4개만 나타냄)

(앞에 -가 붙은 경우는 시작 값을 i=0으로 고정시켰을 경우에 나오는 경우이다. 시작 값을 변화시킴으로써 IIX = XII 처럼 같은 수를 나타내는 경우 한번만 카운트 할 수 있다.)

 

0 0 0 0

0 0 0 1

0 0 0 2

0 0 0 3

 

- 0 0 1 0

0 0 1 1

0 0 1 2

0 0 1 3

 

- 0 0 2 0

- 0 0 2 1

0 0 2 2

0 0 2 3

 

- 0 0 3 0

- 0 0 3 1

- 0 0 3 2

0 0 3 3

 

...

 

 

 

//
//  BF_BOJ16922_로마숫자만들기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

#define I 1
#define V 5
#define X 10
#define L 50

int N;
int answer = 0;
int sum = 0;
bool visited[1001] = {0};
char cArr[4] = {'I','V','X','L'};
int iArr[4] = {1,5,10,50};

vector<int> sumVec;
vector<string> strVec;
string str = "";
void pickDFS(int toPick, int start, int s){
    
    
    if(toPick==0){
        if(visited[s]==false){
            answer++;
            visited[s]=true;
        }
        return;
    }
    
    for(int i = start; i<4; i++){				//시작점을 바꿔서 중복 조합 구현 가능
        pickDFS(toPick-1, i, s+iArr[i]);
    }
    
}


int main(){
    cin>>N;
    pickDFS(N, 0, 0);
    cout << answer;
    
    return 0;
}