[Python 3] BOJ 1366: 기타 코드

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

 

구현하기 굉장히 복잡한 문제였다. 조건들도 많고, 헷갈리거나 실수하기 쉬웠던 포인트들이 많았던 것 같다.

우선적으로 제일 고민히 많이 되었던 포인트는 튜닝되어 있는 줄들을 코드로 만들기 위해서 각자 어떤 줄에 배치할지를 정하는 것이 고민이 많이 되었다. 

 

itertools 라이브러리에 product라는 함수가 있다. 이를 통해 데카르트 곱을 구할 수 있었다.

예시로 product('ABCD', repeat=2)를 이용하면, 

AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD와 같은 output을 얻을 수 있다.

 

1번 입력을 예시로 들어보자. E A D G B E라는 음정을 E G# B로 만들어야 한다. 

그래서 E를 E로 만들고, A를 G#으로 만들고자 한다고 치면,

E가 만들고자 하는 0번째 인덱스이고, G#이 만들고자 하는 1번째 인덱스이기 때문에,

product가 (0,1,...)와 같은 식으로 만들어지는 것이다.

 

하지만 각자 한 개 이상의 소리를 모두 만들어내야 한다. 그렇기에, 모두 (0,0,....0)처럼 되면 모두 E의 음정만 만들어내게 된다.

그래서 len(set())을 이용하여 만들어낸 데카르트 곱의 길이가 중복을 제외하고 한 개씩 하나의 음정을 맡고 있는지 판별하였다.

 

또한 예제 4번째가 어려웠는데, 이 문제에서 나오는 음정들은 옥타브와 상관 없이 배치가 되기 때문에, 눌러야하는 flat의 최댓값과 최솟값을 빼고 1을 더한 값, 그리고 눌러야하는 플랫들을 sort하고 이들의 전 값을 한 옥타브를 올리고 차를 구한 다음에 1을 더한 값과 비교를 하였다,

 

from itertools import product
n,m=map(int,input().split())
tones=list(("A", "A#", "B", "C", "C#", "D", "D#", "E", "F", "F#", "G", "G#"))
current=list(input().split())
code=list(input().split())
answer=1e10
for goal in product(range(m),repeat=n):
    if len(set(goal))!=m:
        continue
    flats=[]
    for k in range(n):
        number=0
        currenttone=tones.index(current[k])
        if tones[currenttone]==code[goal[k]]:
            continue
        while tones[(currenttone+number)%12]!=code[goal[k]]:
            number+=1
        flats.append(number)
    if flats:
        temp=[]
        temp.append(max(flats)-min(flats)+1)
        flats.sort()
        for i in range(1, len(flats)):
            temp.append(1+flats[i-1]+12-flats[i])
        answer=min(answer,min(temp))
    else:
        answer=0
print(answer)