JinWoo Kim

백문이 불여일견, 백견이 불여일행.

3 minute read

1. 로마 숫자 만들기

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

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

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

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

입력

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

출력

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

풀이

import sys
from itertools import combinations_with_replacement
from collections import Counter

N = int(sys.stdin.readline())

rom = {'I': 1,
       'V': 5,
       'X': 10,
       'L': 50}


c = list(combinations_with_replacement(rom,N))

nums = []

for s in list(c):
    tmp = 0
    for r in s:
        tmp += rom[r]
    nums.append(tmp)

nums = len(list(Counter(nums).keys()))
print(nums)

채점 결과

  • 정답

리뷰

  • 4개의 문자를 N번 뽑아 만들수 있는 조합을 살짝 변형하면 답이 나온다.

    • 조합으로 나오는 경우를 모두 출력하고, 각 경우에 나오는 수를 합한후, 중복되는 수를 제거하는 방식으로 진행했다.

  • itertools의 combinations_with_replacement메서드를 활용해 편안하게 구현할수 있었다.

    • 이번 문제에서 나오는 문자의 최대 개수는 20개. 무리없이 조합을 사용할수 있었다.

  • 중복 제거는 Counter를 활용해주었다.

  • Do not reinvent wheel이라는 격언이 있긴 하지만, 메서드 하나로 문제를 날로 먹을때마다 가끔은 죄책감이 들 때가 있다..

2. 동전

  • 여러분은 양팔 저울 하나와 동전 12개(1, 2, …, 12 의 번호)를 가지고 있는데, 그 중 하나는 모조품입니다. 모조품은 다른 동전보다 가볍거나 무겁습니다.

  • 양팔 저울로 세 번 측정하여 모조품을 찾고, 그것이 무거운지 가벼운지 밝히는 프로그램을 작성하세요.

입력

  • 무게를 측정한 결과 데이터가 아래와 같은 형식의 표준 입력으로 주어지게 됩니다.

A B C D x E F G H

  • A, B, C, D, E, F, G, H 는 서로 다른 8 개의 동전들의 숫자이고, x 는 <, >, = 중에 하나입니다. 다음과 같은 의미를 지닙니다.

    • < : A, B, C, D 의 총합은 E, F, G, H 의 총합보다 작다
    • > : A, B, C, D 의 총합은 E, F, G, H 의 총합보다 크다
    • = : A, B, C, D 의 총합은 E, F, G, H 의 총합과 같다

출력

  • 프로그램은 표준출력에 모조품의 번호를 출력하고, 다른 동전보다 무거운 경우에는 + 를, 가벼운 경우에는 - 를 이어서 출력합니다.

세 번의 측정 데이터가 모순되는 경우에는 “impossible” 을 출력해야 합니다.

데이터가 모순되지는 않지만 모조품의 번호를 알아내기에 불충분하거나, 무거운지 가벼운지 알 수 없는 경우에는 “indefinite” 를 출력해야 합니다.

풀이

import sys

nums = [x for x in range(1,13)]
suspect = {'heavy':[], 'light':[], 'innocent':[]}

for _ in range(0, 3):
    line = list(sys.stdin.readline().split())

    left = list(map(int, line[0:4]))
    sep = line[4]
    right = list(map(int, line[5:9]))

    if sep == '>':
        suspect['heavy'] += left
        suspect['light'] += right
        suspect['innocent'] += [x for x in nums if x not in left and x not in right]
    elif sep == '<':
        suspect['heavy'] += right
        suspect['light'] += left
        suspect['innocent'] += [x for x in nums if x not in left and x not in right]
    elif sep == '=':
        suspect['innocent'] += right + left

if suspect['heavy']:
    for s in suspect['heavy'][:]:
        if s in suspect['innocent']:
            suspect['heavy'].remove(s)
        elif s in suspect['light']:
            suspect['heavy'].remove(s)
            suspect['innocent'].append(s)

if suspect['light']:
    for s in suspect['light'][:]:
        if s in suspect['innocent']:
            suspect['light'].remove(s)
        elif s in suspect['heavy']:
            suspect['light'].remove(s)
            suspect['innocent'].append(s)


suspect['heavy'] = list(set(suspect['heavy']))
suspect['light'] = list(set(suspect['light']))
suspect['innocent'] = list(set(suspect['innocent']))

if sorted(suspect['heavy'] + suspect['light'] + suspect['innocent']) != nums:
    print('indefinite')
elif not suspect['heavy'] and not suspect['light']:
    print('impossible')
elif len(suspect['innocent']) < 11:
    print('indefinite')
elif suspect['heavy'] and not suspect['light']:
    print(str(suspect['heavy'][0]) + '+')
elif suspect['light'] and not suspect['heavy']:
    print(str(suspect['light'][0]) + '-')

채점 결과

  • 오답(Index Error)

리뷰

  • 양팔 저울을 사용해 동전을 분류하는 문제이다.

  • 이 문제에서는 모조 동전이 단 한 개인것에 주의한다.

  • 양팔 저울이라 헷갈릴수 있는 부분인데, 이 문제에서 한번 비교할때 세개의 부류가 나오게 된다.

    1. 저울 왼팔에 있는 동전들(left)
    2. 저울 오른팔에 있는 동전들(right)
    3. 저울에 올라가지 않은 동전들
  • 세개로 나뉘는 이유는 다음과 같다.
    • 어느 한쪽이 더 무거울때, 저울에 올라가지 않은 나머지 동전은 모두 무게가 같다.
    • 저울이 평행할때, 저울에 올라가지 않은 동전중에 모조품이 존재한다

  • 단순하게 접근하여 식이 입력될때, 식의 결과에 따라 ‘무거운 동전 의심군’, ‘가벼운 동전 의심군’, ‘무고한 동전군’ 세가지로 분류하여 나누어주었다.

    • 무거운 동전 의심군과 가벼운 동전 의심군에서 동시에 발견된다면, 무고한 동전군으로 변경한다.

    • 저울이 평행하지 않을때, 남은 동전들은 결백하다.

  • 세번의 비교가 끝났을때, 무고한 동전이 11개보다 적다면, 둘중 하나의 상황이다.

    • 비교가 충분히 진행되지 못해 가벼운 동전과 무거운 동전이 각각 하나 이상씩 의심군에 남아있을때.

    • 등호식이 세번 등장하였고, 한번도 분류되지 못한 동전이 있을 경우.
      • 즉, 무거운 동전 + 가벼운 동전 + 무고한 동전의 합이 1~12번 동전 모두를 나타내지 못할때.
    • 어느쪽이던지 비교가 더 필요하다는 의미의 indefinite를 출력.

  • 무거운 동전 의심군과 가벼운 동전 의심군 모두 비어있을때, 어느쪽 데이터가 오류가 발생한것으로 간주. impossible을 출력한다.

  • 나머지 경우 해당 데이터를 출력하면 되는데..

    • 해결을 위한 논리에는 빈틈이 없어보이는데, 정작 채점을 돌려보면 20%즈음에서 IndexError로 실패한다.

    • 적어도 오답이 아닌 IndexError이므로, 배열을 다루는 어딘가에서 나올 반례가 있다는 것이라고 생각할수 있다.

You May Also Enjoy