백준 16922 - 로마숫자 만들기

들어가며

CS의 여러가지 과목 중에 알고리즘은 성적에 있어서는 효자과목이었다. 알고리즘에 대한 이해가 빠른 편이어서 난 알고리즘을 잘하는편이 아닐까 생각했지만, 정작 코딩테스트 예시 문제들을 본 순간 느낀 점은 내가 학부때 수강한 알고리즘 수업만으로는 코테들의 문제들을 절대 풀 수 없을것이다라는 것이다.

동기 그리고 선배들은 어떻게 코테를 뚫고 입사한건지 신기하다는 생각도 들었다.

작년 초 취업한 형을 만났다. 공부할 시간이 어느때보다 넉넉한 지금 시기에 매일 1개씩이라도 알고리즘 문제를 푼다면 나중에 큰 도움이 될거 라는 말을 들었다.
바로 시작하지는 않았지만 GitHub 저장소(daily_algo_challenge)도 만들어서 푼 문제들을 업로드했다.

230여개 가량의 백준문제를 작년 6월부터 풀어오면서 한번도 풀이과정을 올린적이 없었다. 가장 큰 이유는 여전히 나는 알고리즘 풀이를 잘 못한다고 생각했기 때문이다.
또 내가 문제를 이해한 방식을 사람들에게 설명하는게 여간 쉬운일이 아니라고 생각했기 때문이다.

하지만 가끔 재밌는 풀이를 떠올려서 풀 때의 그 기분 좋음을 공유하고 싶어서 앞으로는 신선한 풀이 혹은 흥미로운 문제는 난이도와 상관없이 공유할 계획이다.
실력이 늘어서가 아니다. 나도 그랬으면 좋겠다.

문제 제목

16922번 로마숫자 만들기

문제 설명

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.

하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.

실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.

로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

입력

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

출력

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

예제 입출력

1 : 4
2: 10
10: 244

풀이

일단 아래처럼 문자열로 된 로마숫자를 숫자로 바꿔주는 parser 함수를 정의했다.

def parser(rome_numbers):
  rome_to_num = (('I', 1), ('V', 5), ('X', 10), ('L', 50))

  result = 0
  for char in rome_numbers:
    result += next(x[1] for x in rome_to_num if char == x[0])

  return result

문제를 보면서 가장 먼저 생각 난 풀이는 N이 최대 20이고 10일때 244밖에 되지 않길래 브루트포스를 떠올렸다.

#### brute-force #####
  rome_made = ['I', 'V', 'X', 'L']
  for i in range(1, N):
  new_rome = list()

  for prev in rome_made:
    for k in range(4):
      if not parser(prev + rome[k][0]) in list(map(parser,new_rome)):
        new_rome.append(prev + rome[k][0])
    rome_made = new_rome
    
  print(len(rome_made))
  #####################

new_rome에는 기존의 rome_made에서 4가지 로마 알파벳을 각각 추가해서 중복되지 않게 집어넣는것이다.
그런데 간과한 부분이 시간복잡도였다. 알파벳 4개의 선택지가 있고 N개의 길이의 로마숫자 문자열을 만드려면 O(4^N)개의 로마문자열들 계속 만들어서 검토해야 하는데 그러면 무조건 TLE가 나올수 밖에 없다.

그 다음으로 떠올린 풀이는 DFS를 이용한 조합의 풀이였다. 로마 문자열의 길이가 N이 될때까지 탐색하는데, 길이가 N이 되었을때 만들어진 로마 문자열의 개수를 정답으로 출력하는 것이다.

일단 DFS 풀이를 떠올린 후 특정 로마문자열을 탐색했는지 체크하는 배열이 고민이였다.
처음엔 큰 고민 없이 이런 방식의 풀이를 고려했다.

check 배열은 parser를 통해서 로마 문자열이 변환된 숫자를 기준으로 이전에 탐색한 것인지 아닌지 체크하게 두었다.

check=set()
...
...
def dfs(length, current_rome, result_rome):
  # N자리 로마숫자를 완성했으면 결과 리스트에 넣어줌
  if length == N:
    result_rome.append(current_rome)
    return
    
  for k in range(4):
    if not parser(current_rome + rome[k]) in check:
      dfs(length + 1, current_rome + rome[k], result_rome)
      check.add(parser(current_rome + rome[k]))
...
...

하지만 이 구현은 문제가 발생했는데 만약 IX(1+10) 를 먼저 방문하고 IVV(1+5+5) 를 방문하려 하면 이미 11을 방문한것으로 봐서 IVV를 탐색하지 않는것이다.

BFS와 DFS든 노드의 방문여부 배열의 차원을 구성하는것은 노드를 방문할때의 상황의 개수에 따라 나뉘어진다는 사실을 떠올렸다.

비슷한 예시로 백준 2206번 벽 부수고 이동하기가 있다.
탐색에 있어서 현재 위치의 x,y좌표와 벽을 부수었는지 부수지 않았는지에 따라서 방문배열의 차원이 3차원으로 구성된다.

노드를 방문할때 상황이 어떻게 달라지나 생각해보았다.

첫번째로 당연히 parser 함수에 의해 로마 문자열이 변환된 숫자가 있고 두번째로는 로마 문자열의 길이였다. IX는 길이가 2일때 11을 방문한것이고, IVV는 길이가 3일때 11을 방문한 것이니 서로 다른 노드를 방문한것이다. 그렇기에 이 탐색에서 방문 배열은 2차원으로 구성해야 하는것이다.

코드를 아래와 같이 수정하고 AC를 받을수 있었다.

for k in range(4):
    # 백트래킹 적용되는 부분
    # 체크리스트에 로마자를 변환한 숫자와 길이가 동시에 있는 이유는
    # IVV와 IX는 둘다 같은 11을 의미하는데 IVV와 IX 모두 방문해야 하기때문에
    # 로마자 숫자의 길이도 기록
    if not (parser(current_rome + rome[k]), length) in check:
      dfs(length + 1, current_rome + rome[k], result_rome)
      check.add((parser(current_rome + rome[k]), length))

방문배열이라고 볼수도 있지만 check는 백트래킹을 검사하는 수단이라고도 볼수 있을것 같다.