백준16922 - 로마 숫자 만들기

www.acmicpc.net/problem/16922

16922번: 로마 숫자 만들기

파이썬으로 갈아탄지 2일차인데 생각보다 C++이랑 많이 달라서 고생중이다. 먼저 내장 함수들을 익혀야겠다.

 

이 문제는 백트래킹을 이용하면 금방 풀리는 문제이다. 주의할 점은 다음과 같다.

1. XXI와 XIX는 같으니까 이것을 걸러줘야 한다. 따라서 현재 탐색한 위치에서 뒤에 오는 인덱스는 다시 탐색하지 않고 현재 인덱스부터 탐색하게 하였다.

 

이것만 주의한다면 쉽게 풀 수 있다. 다른 어려운 난이도도 있는데 나중에 도전해봐야겠다.

def matchNumber(rome):
  if rome == 'I':
    return 1
  elif rome == 'V':
    return 5
  elif rome == 'X':
    return 10
  elif rome == 'L':
    return 50

def solution(arr, nowNumber, idx, loop, N, romeNumbers):
  if(loop == N):
    arr[nowNumber] = True
  else:
    for i in range(idx, len(romeNumbers)):
      nowNumber += matchNumber(romeNumbers[i])
      solution(arr, nowNumber, i, loop + 1, N, romeNumbers)
      nowNumber -= matchNumber(romeNumbers[i])

arr = [False] * 1001
N = int(input())

solution(arr, 0, 0, 0, N, ['I', 'V', 'X', 'L'])

results = len([x for x in arr if x == True])
print(results)