코딩마스터스 (고급) 작곡 프로그램

- 문제설명
작곡가 미넷은 지금까지 수많은 곡을 작곡 해 왔습니다. 더이상 새로운 창작물을 만들어 낼 수 없는 경지에 이르렀습니다. 더이상의 곡 진행을 떠올릴 수 없게 된 미넷은, 컴퓨터를 사용해 새로 작곡할 악곡의 코드 진행을 만들기로 했습니다.

미넷은 음악을 만드는 데 있어 총 14가지의 코드만을 사용합니다. 그것들은 A, B, C, D, E, F, G의 메이저 코드들과, Am, Bm, Cm, Dm, Em, Fm, Gm의 마이너 코드들입니다. 이 14가지의 코드들을 사용해 5마디로 나누어져 있는 악보를 제각기 다른 코드들로 채우려고 합니다. 예를 들어, 5마디를 다음과 같이 채울 수 있습니다.

F | Em | Am | C | Dm

그런데, 미넷은 권위있는 작곡가이기 때문에, 자신의 곡을 작곡할 때에 지키는 조건이 있습니다. 그 조건은 다음과 같습니다.

1. 14개의 코드들은 각각 한 번을 초과하여 사용할 수 없습니다.
2. "너무 뻔한 코드의 진행"을 사용하지 않습니다.
3. 메이저 코드와 마이너 코드는 a번을 초과하여 연속되어선 안 됩니다. (1 ≤ a ≤ 5)

"너무 뻔한 코드의 진행"이란, 작곡가 미넷이 지금껏 작곡을 해 오면서 너무나 자주 써 왔던 코드 진행을 말합니다. 이 "너무 뻔한 코드의 진행"은 코드 2개의 길이를 갖습니다.

"너무 뻔한 코드의 진행"의 예시는 다음과 같습니다.

F Cm
Cm G

메모의 각 줄은 "너무 뻔한 코드의 진행" 으로 첫 번째 줄은 F 코드 뒤에 Cm 코드가 나올 수 없음을 의미하고 두 번째 줄은 Cm 코드 뒤에 G 코드가 나올 수 없음을 의미합니다.

컴퓨터는 5마디로 구성된 여러 코드 진행들을 제안할 수도 있고, 제안할 수 있는 코드 구성이 존재하지 않을 수도 있습니다. 코드 2개로 구성된 "너무 뻔한 코드의 진행"이 N개 주어졌을 때, 작곡가 미넷이 제시하는 조건들을 만족하는 코드 진행이 몇 가지인지 구하는 프로그램을 작성해 주세요.

- 입출력 예
입력 #1
2 1
F Cm
Cm G

입력 #2
0 5

- 입력값 설명
입력의 첫째 줄에 미넷이 메모한 "너무 뻔한 코드의 진행"들의 개수 N과 메이저나 마이너 코드가 연속해서 나올 수 없는 횟수 a가 주어집니다. (0 ≤ N ≤ 50, 1 ≤ a ≤ 5)
두번째 줄부터 N개의 줄에 걸쳐 "너무 뻔한 코드의 진행"들이 주어집니다. "너무 뻔한 코드의 진행"의 코드들은 띄어쓰기로 구분되어 주어집니다.

 

출력 #1
16290

출력 #2
240240

- 출력값 설명
본문의 조건들을 만족하는 코드 진행의 수를 출력합니다.
만약 조건을 만족하는 코드 진행이 존재하지 않는 경우, 조건을 만족하는 코드 진행의 수는 0이므로, 0을 출력해야 합니다.

 

 

- 풀이과정

저는 이 문제를 백트래킹을 사용하여 풀었는데요!

백트래킹은 재귀호출을 통해 가능한 조합을 탐색하는 과정인데, 완전탐색과의 차이점은 조건에 맞지 않은 경우는 제외한다는 점이 다르다고 합니다.

7개의 마이너와 7개의 메이저 코드를 합해서 14개의 문자열을 Map을 통해 숫자로 변환하여 사용했고, 이 MAP을 통해 뻔한 코드들도 숫자로 변환하여 조건으로 사용할 Boolean배열을 만들었습니다. (첫번째 코드는 앞에, 두번째 코드는 뒤에 넣는걸로)

백트래킹으로 사용할 수 있는 함수들을 static으로 지정해놓았습니다.
major_count 와 minor_count 메이저와 마이너가 횟수를 초과했는지, 그리고 5마디를 확인하는 Level과 

14가지의 뒷코드를 알려줄 i를 반복문을 통해 탐색합니다.

중복 코드가 없으며 (used)

메이저, 마이너 코드가 a번을 초과하지 않고

뻔한 코드 진행이 아닌 5마디를 찾아 탐색하는 방식을 사용했습니다.

import java.io.*;
import java.util.*;

public class Main {
    static int a = 0; // 연속해서 나올 수 없는 횟수
    static int result = 0; // 백트래킹 결과
    static String[] codes = {"A", "B", "C", "D", "E", "F", "G", "Am", "Bm", "Cm", "Dm", "Em", "Fm", "Gm"};
    static Map<String, Integer> codemap = new HashMap<>();
    static boolean[][] prohibit = new boolean[14][14]; // 뻔한 코드 금지
    static boolean[] used = new boolean[14]; // 코드 사용 여부

    public static void main(String[] args) throws IOException { 
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        a = scanner.nextInt(); 

        for (int i = 0; i < codes.length; i++){
            codemap.put(codes[i], i); // 모든 코드에 숫자 부여
        }

        for (int i = 0; i < n; i++){ // 뻔한코드 한줄씩 받기
            int code1 = codemap.get(scanner.next()); // 뻔한 코드1 = 앞부분
            int code2 = codemap.get(scanner.next()); // 뻔한 코드2 = 뒷부분
            prohibit[code1][code2] = true;
        }
        scanner.close();

        // 백트래킹
        function(0, 0, 0, -1);
        
        System.out.println(result);
    }

    static void function(int major_count, int minor_count, int level, int before){
        if (level == 5){ // 5마디 완성
            result++;
            return;
        }
        
        for (int i = 0; i < 14; i++){
            if (used[i]) continue; // 사용한 코드 확인(마디로 지정된 코드)
            boolean major = i < 7; // 메이저면 true
            if (major && major_count >= a) continue; // 메이저 a번 초과
            if (!major && minor_count >= a) continue; // 마이너 a번 초과
            if (before != -1 && prohibit[before][i]) continue; // 너무 뻔한 코드 진행인지 확인

            used[i] = true; // 사용 완료 (마디로 지정)
            function(major ? major_count + 1 : 0, major ? 0 : minor_count + 1, level + 1, i);
            used[i] = false; // 사용 완료 후 되돌리기 
        }
    }
}