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

[백준 온라인 저지 링크]

16922번: 로마 숫자 만들기

로마자 조합의 순서를 따지지 않는다는 조건을 통해 중복조합을 구하는 문제임을 알 수 있는데요, 따라서 N과 M 4번과 형태가 매우 유사하지만 같은 코드로 풀면 N=6 부터 답이 달라지기 시작합니다.

 

왜냐하면 바로 "조합의 합이 같은 경우" 가 생기기 때문인데요, 한번 예시를 들어보겠습니다.

// N(뽑아야 하는 수)이 2일 때

(N과 M)  =>  (로마자)
 1 1        I I (2)
 1 2        I V (6)
 1 3        I X (11)
 1 4        I L (51)
 2 2        V V (20)
 2 3        V X (15)
 2 4        V L (55)
 3 3        X X (20)
 3 4        X L (60)
 4 4        L L (100)

N이 2일 때에는 로마자로 구한 숫자들이 겹치지 않습니다.

따라서 경우의 수는 10가지가 되고, 이는 테스트케이스와 일치합니다.

// N(뽑아야 하는 수)이 6일 때

   (N과 M)    =>   (로마자)
     ...            ...
 1 1 1 1 1 4     I I I I I L (55)
     ...            ...
 4 3 3 3 3 3     V X X X X X (55)

그런데 N이 6일 때, 보이시나요?

분명 다른 수의 조합을 뽑았지만 로마자의 합을 구해보니 같은 55가 되는 경우입니다.

 

이로 인해 N=6 일때부터 결과가 점점 어긋나게 되고, 따라서 재귀 종료조건에 다다르면 카운팅을 1 더하고 리턴하는 방식으로는 문제를 풀 수 없습니다. (슬픈 경험담입니다 😂)

[정답 코드 - Python]

N = int(input())
number = [1, 5, 10, 50] # 로마자 배열
numberList = []
sumList = [0] * 1001 # 로마자의 합이 담기는 배열 (1 <= N <= 20이니, 인덱스가 1000까지 필요함)


def backtrack(depth, num):
    try:
        if depth == N:
            sumList[sum(numberList)] = 1
            return

        for i in range(num, 4):
            numberList.append(number[i])
            backtrack(depth + 1, i)
            numberList.pop()
    except:
        print(len(sumList))


backtrack(0, 0)
print(sum(sumList))

따라서 경우의 수를 카운트하는 것보다는 로마자의 합이 되는 수들의 배열을 만들고, 해당 배열의 길이를 출력하도록 함으로써 문제를 푸실 수 있습니다.