[BOJ][Python]1366 풀이

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

1366번: 기타 코드

def f(string_idx, result):
    if len(result) == n:
        for i in visited:
            if i == 0:
                return
        else:
            if max(result) == 0 and min(result) == 0:
                ans.append(0)
            else:
                sorted_result = sorted(result)
                tmp = []
                max_result = sorted_result[-1]
                min_result = 0
                for i in sorted_result:
                    if i != 0:
                        min_result = i
                        tmp.append(max_result - min_result)
                        break
                for i in range(1, len(sorted_result)):
                    if sorted_result[i-1] != 0:
                        tmp.append(sorted_result[i-1] + 12 - sorted_result[i])
                ans.append(min(tmp) + 1)
    else:
        for j in range(m):
            visited[j] += 1
            result.append(frets[string_idx][j])
            f(string_idx+1, result)
            visited[j] -= 1
            result.pop()
            
n, m = map(int, input().split())
strings = input().split()
chords = input().split()
notes = {'C': 0, 'C#': 1, 'D': 2, 'D#': 3, 'E': 4, 'F': 5, 'F#': 6, 'G': 7, 'G#': 8, 'A': 9, 'A#': 10, 'B': 11}
frets = [[] for _ in range(n)]
for i in range(n):
    for j in chords:
        frets[i].append((notes[j]-notes[strings[i]]+12)%12)
ans = []
visited = [0 for _ in range(m)]
f(0, [])
print(min(ans))

사실 올릴까 말까 좀 고민을 많이 했습니다. 요근래 들어서 짠 코드 중에 제일 뒤죽박죽으로 짠 코드가 아닌가 싶어서 최적화를 시켜서 풀이를 작성할까 했는데 너무 이 문제에 매달려 있으면 다른 일을 못하니까 그냥 올리기로 마음 먹었습니다.

 

이것도 처음에 문제에서 설명이 애매한 부분이 있어서 좀 헷갈렸는데 이 문제에서 중요한 부분을 간단히 짚고 넘어가자면,

1. 하나의 줄에서 주어진 코드에 있는 음을 무조건 하나 내야하고, 주어진 코드의 모든 음은 연주되어야 한다.

2. 프렛을 누르지 않은 줄은 난이도 계산에 사용하지 않는다. 즉, 난이도 계산은 프렛을 누른 줄만 사용한다.

3. 난이도의 계산은 가장 높은(번호가 큰) 프렛과 가장 낮은(번호가 작은) 프렛 그 둘의 번호의 차에 1을 더한다.

4. 옥타브와 상관없이 같은 이름은 같은 음으로 생각한다.

 

지금부터는 위의 조건에 대한 부연 설명을 할테니까 이미 안다고 생각하시면 굳이 보지 않으셔도 됩니다.

 

먼저 1번입니다. 당연한 소리 같지만 해당 문제는 줄의 갯수와 코드의 갯수에 따라 각각의 줄이 전부 다른 음을 연주할 수도 있고 중복되는 음을 연주할 수도 있습니다. 그 말인 즉, 여러 줄에서 같은 음을 낼 때, 그 중에서 가장 효율적으로 그 음을 낼 수 있는 줄을 사용해야 비교적 운지 난이도가 줄어든다는 얘기죠. 그리고 거기에 더해 주어진 코드의 모든 음을 내야 하기 때문에 코드와 줄을 비교해가면서 어떤 줄이 어떤 음을 냈을 때 가장 운지 난이도가 낮아지는지 확인해야 합니다. 그리디 또는 브루트포스일 가능성이 있겠네요.

 

2번입니다. 이 부분이 초반에 은근히 헷갈렸는데요. 프렛을 누르지 않는 줄은 절대 난이도 계산에 사용하지 않습니다. 예를 들어서 C D의 2줄이 주어지고 C# D의 2개 음이 주어졌을 때 운지 난이도는 가장 높은 프렛{C#(1)} - 가장 낮은 프렛{D(0)} + 1 = 2가 아니라 C# - C# + 1 = 1 입니다. 누른 프렛이 C# 하나뿐이니까 높은 프렛도 낮은 프렛도 C# 하나뿐인거죠. 마찬가지로 주어진 입력이 C#이 아니라 F든 A든 높은 프렛과 낮은 프렛이 같기 때문에 난이도는 1이 됩니다(예제 3번에 있듯이 아예 프렛을 누르지 않을 경우는 0 - 0 + 1의 1이 아니라 그냥 계산을 하지 않는 0입니다). 헷갈리지 않도록 주의해주세요.

 

3번입니다. 2번 설명하면서 좀 많이 해버려서 그냥 넘어가겠습니다. 난이도 계산 시에는 + 1을 해주어야 한다는 점 잊지 마세요.

 

4번입니다. 사실 질문탭에 어떤 분이 남겨놓은 내용을 보고 저도 약간 혼동이 왔었습니다. 그 내용을 요약하자면,

예제 4번의 경우 E와 F의 줄, F#과 D#의 음이 주어졌을 때 이걸 난이도 계산을 하면 E가 F#이 되어 2번 프렛, F가 D#이 되어 10번 프렛을 누르고 10 - 2 + 1 = 9 해서 9가 정답이 되어야 하는데 예시 출력이 3이다. 문제가 잘못 되었다.

라는 내용입니다. 저도 처음엔 어 그러네 싶어서 잘못된 문제니까 그냥 풀지 말고 넘어갈까 했는데, 이미 푼 사람들이 있으니까(물론 맞춘 분이 별로 없는 문제긴 합니다만) 그럼 그 사람들이 다 잘못된 문제를 풀기 위해 일부러 틀린 코드를 작성했나? 하는 생각이 드니까 아닌 것 같더라구요. 그래서 고민을 좀 해보니까, 프렛의 상한이 주어지지 않았다는 점이 생각났습니다. 어라? 프렛의 상한이 없네? 어라? 옥타브에 상관없이 같은 음으로 생각한다고 하네? 그럼 차이가 많이 나면 아예 12프렛을 올려서 높은 옥타브를 치면 난이도가 낮아지는 거 아닐까? 하는 생각까지 들었을 때 비로소 문제를 풀 방법이 보였던 것 같습니다. 사설이 길었습니다만 해당 조건을 풀어 정리하자면, 운지 난이도가 높다면 가장 낮은 프렛의 음을 한옥타브 올려서 난이도를 낮출 수 있겠다 입니다.

 

코드 설명입니다. 저는 처음에 그리디를 생각했었는데 항상 최소의 프렛을 선택할 경우 주어진 모든 음을 연주하지 못하는 경우가 생기더라구요. 그 다음으로는 브루트 포스를 생각했는데 입력의 길이가 주어지기 전에는 모르니까 단순한 반복문으로는 풀지 못하겠고 백트래킹을 써야겠구나 하는 생각이 들었습니다(물론 풀고 나서 다른 분들 풀이를 보니까 재귀를 안쓰고도 푸신 분들이 있으신 걸 보면 뭔가 제가 또 비효율적인 방법을 썼나보다 싶긴 합니다. 언젠간 최적화를 해서 풀이를 갱신해보도록 하겠습니다). 그래서 먼저 각 줄에서 각 음을 연주하기 위한 최소 프렛을 전부 저장하고 거기에 대해서 백트래킹을 진행합니다. 주어진 음이 모두 연주되는지를 체크하기 위해 방문처리용 visited 리스트를 만들어서 visited의 원소 중 하나라도 0이라면 연주가 안되었다는 뜻이니 탈출을 하고 전부 0이라면 해당 케이스에 대해 난이도를 계산합니다. 난이도 계산시 처음에는 기존의 최대 프렛과 최소 프렛의 차를 구하고, 그 다음부터는 최소+12프렛과 원래 최소 프렛의 바로 다음 작은 프렛과의 차를 구합니다(최소 프렛이 옥타브가 올라가면서 더 이상 최소가 아니기에 새로이 최소가 된 프렛과의 차를 구하기 위해서입니다). 그 과정을 주어진 줄의 갯수(정확하게는 프렛이 눌러진 줄의 갯수)만큼 반복해서 그 중의 최솟값에 + 1을 한 값을 저장합니다. 마지막으로 그 모든 저장된 값들 중에서 최솟값을 출력하면서 코드가 끝이 납니다.

 

말로 풀어서 써 놓으니 많이 복잡해보이실 것 같습니다. 잘 이해가 가지 않으신다면 예제 입력을 사용해서 직접 디버깅을 진행하면서 보시면 훨씬 이해가 편하실겁니다. 저는 처음 재귀를 배울 때에도 머리로 생각하려니 엄청난 횟수로 들락날락하는 재귀의 특성상 어느 순간 흐름을 놓치면서 이해가 안되더라구요. 각자가 사용하시는 ide의 디버깅 모드를 잘 활용하면 정말 큰 도움이 됩니다. 정확하게 언제까지 코드 최적화를 시킨다고 장담은 못하겠지만, 그래도 빠른 시일내에 해보도록 하겠습니다.