[BOJ] 16438. 원숭이 스포츠

분할정복을 이용하여 해결할 수 있던 문제였다.

이 문제 같은경우 맨처음 문제자체를 이해하지 못하였다. 하지만 분할정복이라는게 떠올랐고, 머지소트와 비슷한 원리로 접근해보았다. 우선 7일을 출력하기 위해 result란 이차원배열을 만들어두고, 분할정복을 시도하였다. 우선 start와 end값을 받고, 이들의 중간값인 mid를 구하게 된다. 이렇게 start~mid, mid~end 까지 두 그룹으로 나누고 알파벳을 각 각 배정해준다. 이렇게 되면 두그룹은 서로 한번은 적으로 만나는 것이 보장이되게 된다. 이런식으로 재귀호출하여 분할정복을 적용해보았다. 단 맨끝 결과에 오로지 B로만 차있는 경우가 생기게 되는데 이경우엔 A를 임의로 하나 넣어주었다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main_bj_16438_원숭이스포츠 {
    static int N;
    static char[][] result;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
 
        result = new char[7][N];
 
        func(0, 0, N);
 
        for (int i = 0; i < 7; i++) {
            if (!Arrays.asList(result[i]).contains("A")) {
                result[i][0] = 'A';
            }
            for (int j = 0; j < N; j++) {
                System.out.print(result[i][j]);
            }
            System.out.println();
        }
    }
 
    static void func(int depth, int start, int end) {
        if (depth == 7) {
            return;
        }
 
        int mid = (start + end) / 2;
 
        for (int i = start; i < mid; i++) {
            result[depth][i] = 'A';
        }
 
        for (int i = mid; i < end; i++) {
            result[depth][i] = 'B';
        }
 
        func(depth + 1, start, mid);
        func(depth + 1, mid, end);
    }
}