[Algorithm] 백준_16922번: 로마 숫자 만들기

오늘의 문제는 🚀 백준 16922번: 로마 숫자 만들기이다.

왜 맨날 어려울까.. 슬프다

대충 콤비네이션으로 계산했을 때, 4^20개의 경우가 나와서 어떻게 해야하지 고민을 많이 했다.

고민고민하다 힌트를 얻어서 풀어보니, n개를 각각 잘 배분해서 중복을 없애는 방법이 답이라고 생각했다.

테스트케이스 이해하기

처음에 콤비네이션을 구한 다음에 중복한 n개 만큼 더해주면 될거라 생각해서 간단할 줄 알았는데, 아니였다.

여러 방식으로 곱해보고 생각하는 시간을 많이 가졌다!

알고리즘

1. 중복을 없애기 위해 set 선언
2. 삼중 for문을 활용해서 n을 i, j, k, 나머지로 나눈다.
3. 각각의 값에 가중치를 곱해서 set에 추가해준다.
4. set의 길이를 프린트해주면 끝!

정답코드

n = int(input())
unique = set([])

#n개를 나눠가지기 위해
for i in range(n+1):
    for j in range(n+1-i):
        for k in range(n+1-i-j):
            unique.add(1*i+5*j+10*k+50*(n-i-j-k))

print(len(unique))

🚀Reference: 백준 16922번 - 로마 숫자 만들기