[알고리즘] 백준 16922 파이썬 - 로마 숫자 만들기

 

16922번: 로마 숫자 만들기

 

문제

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

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

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

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

 

문제풀이

from itertools import combinations_with_replacement
n=int(input())
ans=set()
arr=[1,5,10,50]
for combi in combinations_with_replacement(arr, n):
    ans.add(sum(combi))
print(len(ans))

- itertools의 combinations_with_replacement를 사용했다.

- 이는 중복을 포함하여 모든 조합을 만든다.

- 아래의 사진처럼 2자리수로 이루어질 수 있는 10개의 조합을 계산해준다.

- 이후 ans에 그 조합의 합을 중복없이 추가해주고 그 길이를 출력해준다.