[백준 | 실버3] 16922번: 로마 숫자 만들기(중복조합)

https://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개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.

예제 입력 1 복사

1

예제 출력 1 복사

4

I, V, X, L을 만들 수 있다.

예제 입력 2 복사

2

예제 출력 2 복사

10

2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다.

예제 입력 3 복사

10

예제 출력 3 복사

244

 

문제풀이

로마자 조합의 순서를 따지지 않는다는 조건을 통해 중복조합을 구하는 문제임

 

 

문제해결

[1, 5, 10, 50]을 중복을 허용해서 n개 뽑는 리스트 조합을 생성해준다.

 

중복 조합은 from itertools import combinations_with_replacement를 이용하면 쉽게 구할 수 있다.

중복조합 :  combinations_with_replacement([반복가능한 개체], 길이)

 

중복조합으로 조합리스트를 만들어 준 후 조합 종류를 sum 해준다.

sum 해준 값에 중복이 존재 하므로 set을 통해서 제거 해준 후 남은 조합의 합의 개수가 몇개인지 확인

 

중복을 허용한 조합 : combinations_with_replacement

만들 수 있는 서로 다른 수의 개수 : set()

from itertools import combinations_with_replacement

n = int(input())
num_list = [1, 5, 10, 50]
result = []
#중복조합 리스트 : combinations_with_replacement([반복가능한 개체], 길이)
#[1, 5, 10, 50]에 있는 숫자를 n개 뽑는다(중복 가능)
com_list = list(combinations_with_replacement(num_list, n))

#중복조합으로 n개 뽑은 종류 리스트를 더해준다.
for i in com_list :
    result.append(sum(i))

print(len(set(result)))     #더한 값이 중복값일 수 있어서 set이용

 

 

•  

문제해결

DFS를 이용해서 중복조합 만들기

n개를 뽑아 만든 값을 새로운 배열에 추가하기 위해서는 com_list[:] 가 필요했다.

(com_list.pop()을 해주기 pop이 되어서 빈 배열로 들어가므로 포인터 개념으로 빈 배열에 접근하는 문제, 

문자열 슬라이스를 통해서 com_list를 복사해서 new_com_list로 넘겨준다고 생각해야한다)

import sys

n = int(input())
num_list = [1, 5, 10, 50]
com_list = []
new_com_list = []
result = []

def DFS(L, start_index) :
    if L == n :
        new_com_list.append(com_list[:])    #com_list복사를 위해 일부러 문자열 슬라이스 적용
        return
    else :
        for i in range(start_index, len(num_list)) :
            com_list.append(num_list[i])
            DFS(L+1, i)
            com_list.pop()

DFS(0, 0)
for i in new_com_list :
    result.append(sum(i))

print(len(set(result)))