[Python/백준] 16922. 로마 숫자 만들기

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

순열과 조합

https://www.acmicpc.net/problem/16922

---

1차 시도) 실패

import sys
from itertools import combinations_with_replacement

input = sys.stdin.readline

# 로마 숫자 문젠데, 그냥 단순히 더하기로 한다.
# 로마 숫자 N개를 사용해 만들 수 있는
# 서로 다른 수의 개수는?
# 즉, 1, 2, 3, 4의 숫자가 있을 때, (실제론 0 1 2 3)
# 이 숫자들로 순서 고려하지 않고, 중복 허용해서 n개 뽑아
# 만들 수 있는 모든 수의 경우의 수를 구하면 됨.
# 즉, 중복 조합 4Hn을 구하면 됨.

# 입력 : 사용할 수 있는 문자 개수 N
# 출력 : 만들 수 있는 경우의 수
def combinations_with_replacement(current, start):
    if len(current) == n:
        global counts
        counts += 1
        return
    for i in range(start, 4):
        current.append(i)
        combinations_with_replacement(current, i)
        current.pop()

n = int(input())
counts = 0
combinations_with_replacement([], 0)

print(counts)
#이거 실제론 중복이 가능하다!!
#ex. 1*10+50*2 = 10*12 = 120
#따라서 실제 1 5 10 50으로 두고, 
# set에 넣으며 중복 제거되게 하면 바로 될듯
# answer을 set으로 하자!!

2차 시도) 성공

3번째 테케에서 기존 수보다 더 큰 경우의 수가 출력되는 것에서 착안, 중복이 있다는 것을 깨닫고 예시를 들어보니 1*10+50*2 = 10*12 = 120 와 같이 수의 합에 따라 중복이 존재함.

따라서, answer을 set으로 두고 set에 add해가면서 더함. 자동중복제거.

# 틀림
import sys
from itertools import combinations_with_replacement

input = sys.stdin.readline

# 로마 숫자 문젠데, 그냥 단순히 더하기로 한다.
# 로마 숫자 N개를 사용해 만들 수 있는
# 서로 다른 수의 개수는?
# 즉, 1, 2, 3, 4의 숫자가 있을 때, (실제론 0 1 2 3)
# 이 숫자들로 순서 고려하지 않고, 중복 허용해서 n개 뽑아
# 만들 수 있는 모든 수의 경우의 수를 구하면 됨.
# 즉, 중복 조합 4Hn을 구하면 됨.

# 입력 : 사용할 수 있는 문자 개수 N
# 출력 : 만들 수 있는 경우의 수
def combinations_with_replacement(current, start):
    if len(current) == n:
        answer.add(sum(current))
        return
    for i in range(start, 4):
        current.append(numbers[i])
        combinations_with_replacement(current, i)
        current.pop()

numbers = (1, 5, 10, 50)
n = int(input())
answer = set()
combinations_with_replacement([], 0)

print(len(answer))

강사님 풀이 확인)

import sys
input = sys.stdin.readline


def combinations_with_replacement(counts, start, total):
    if counts == n:
        totals.add(total)
        return

    for i in range(start, len(numbers)):
        combinations_with_replacement(counts + 1, i, total + numbers[i])


n = int(input())
numbers = [1, 5, 10, 50]
totals = set()

combinations_with_replacement(0, 0, 0)

print(len(totals))

내가 ‘current’와 ‘answer’로 한 동작을, ‘counts’와 ‘total’로 구현하였다.

이러면 외부에 해당 변수들을 선언할 필요가 없어짐.

dfs에서, 내가 조작해서 결과에 포함시켜야 하는 변수가 있다면, 그냥 dfs 함수의 매개변수로 넣어버리는 아이디어!! 기억하자.

---

250223 재풀이

from itertools import combinations_with_replacement

import sys
input = sys.stdin.readline

# 입력 : 로마 숫자 n개
# 출력 : 만들 수 있는 모든 수의 개수

# 중복o 순서x -> 조합인데, 중복조합

# 5 * 10 -> 10 10 10 10 5 1 1 1 1 1 -> 50
# 따라서, 그 합을 가지고 중복을 제거해줘야함 -> set에 집어넣자.

n = int(input())
roman_numbers = (1, 5, 10, 50)
answer = set()

for combination in combinations_with_replacement(roman_numbers, n):
    answer.add(sum(combination))

print(len(answer))