[Baekjoon] 16922_로마 숫자 만들기

Silver III

문제(출처: https://www.acmicpc.net/problem/16922)

---

<로마 숫자 만들기>

문제 

 

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고,
이 문제에서 다른 문자는 사용하지 않는다.
하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은,
각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.
실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경 쓰지 않는다.
예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.
로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

 

입력

 

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

 

출력 

 

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

 

 

문제 풀이

   - my solution

import sys
from itertools import combinations_with_replacement # 중복 조합

if __name__=='__main__':
    n=int(sys.stdin.readline().strip())

    num=[1,5,10,50]
    arr=set() # 서로 다른 수 만들기 위해 set 선언

    for i in combinations_with_replacement(num, n):
        arr.add(sum(list(i)))

    print(len(arr)) # 길이 출력

 

맨 처음 코드를 구현 후 빼먹은 조건은 "만들 수 있는 서로 다른 수의 개수"를 구하는 것이었다.

 

• 이 문제에서 순서는 신경 쓰지 않으므로 중복 조합을 이용한다.
• 서로 다른 수의 개수를 count 하기 위해 set을 이용한다.
• 개수를 구하는 것이므로 최종 set의 길이를 출력한다.

---

생각🤔

 

중복 조합을 사용하는 방법을 몰라 찾아봤더니 python에 조합형 itertools가 있어 활용해볼 수 있었다.

 

*다음번에 라이브러리를 사용하지 않고 조합과 순열을 구현해보는 것을 공부해봐야겠다.

 

---