[백준][파이썬] 16922번 로마 숫자 만들기

문제 번호 : 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

---

Code

import itertools

n = int(input())
rome = [1, 5, 10, 50]


comb = list(itertools.combinations_with_replacement(rome, n))
data = set([])
for t in comb:
    data.add(sum(t))

print(len(data))

조합(Combination) 문제라 생각하고 itertools를 사용해서 문제를 풀어봤다. rome이라는 데이터셋에서 n개의 데이터를 반복이 되도록 조합한다. comb 리스트 안에 각 원소들은 tuple 자료형이다. 그냥 조합만을 사용해서 했을 경우에는 합이 중복되는 경우가 존재했고 data라는 집합 자료형에 각 튜플들의 합을 넣어주면서 중복을 피했다.

중복이 일어나는 예시로는 n이 6인 경우 XXXXXV 와 LIIIII 이 둘 다 55의 값을 가지게 된다.

 

※주의할 점

• combinations_with_replacement()의 반환 형태가 class로 존재하며 이것을 iterable한 자료형으로 바꿔주어야 한다. 
• 집합 자료형은 중복을 허용하지 않고 인덱스를 가지지 않는다.

 

다음 코드는 itertools를 import하지 않고 반복문을 사용한 코드이다.

n = int(input())
rome = [1, 5, 10, 50]
result = set([0])
for _ in range(n):
    result = set([i + j for i in result for j in rome])

print(len(result))

처음에 n 만큼 반복하면서 result에 원소들을 넣는 것이 아니라 완전히 새로운 집합으로 만든다.

위의 for 문와 비슷하게 다음 코드를 조금 더 보기 쉽게 만든 것이다.

tmp = []
for _ in range(n):
    for i in result:
        for j in rome:
            tmp.append(i + j)
    result = set(tmp)
    tmp = []