[Python] 백준 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

 

 

 

 

풀이방법 

---

문제를 처음봤을땐 순서를 고려하지않는 모든 중복조합의 갯수를 count 하는 방법을 이용하려 했지만

중복조합에서도 나오는 수의 합이 같은 경우가 존재한다

 

I I I I I L (55) >>> 1 1 1 1 1 50

V X X X X X (55)>>>5 10 10 10 10 10

 

위에 예시와 같이 뽑은 조합은 다르지만 나오는 수 값이 동일한것이 존재해 중복을 없애주는 작업이 들어가줘야 한다

 

이 때 중복조합 리스트는 파이썬 기본 라이브러리인

itertools 에 combinations_with_replacement([반복가능한 개체],길이) 을 통해 쉽게 리스트를 얻을 수 있다

이 때 반환받은 리스트의 합을 for 문을 이용 

 

sum(리스트) 을 이용해 얻은후 다른 리스트에 삽입해 준다 

 

최종 리스트를 파이썬 set(list) 으로 변환해 중복을 제거해 준후

 

len() 을 이용해 최종 갯수를 리턴해 주면된다

 

코드

---

 

 

 

from itertools import combinations_with_replacement
k= int(input())
dataset = [1, 5, 10,50]
temp = list(combinations_with_replacement(dataset, k))
result = []
for i in temp:
    result.append(sum(i))
print(len(set(result)))