21.09.11 TIL

백준 코딩 문제

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

2447 별 찍기

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3^k이며, 이때 1 ≤ k < 8이다.

첫째 줄부터 N번째 줄까지 별을 출력한다.

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

NxN 2차원 배열과 재귀 방식으로 해결하려 했으나, 시간 초과...

public class Q2447 {
    static char[][] board;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());

        board = new char[n][n];
        recursive(n, 0, 0, true);

        for (int i = 0; i < board.length; i++) {
            System.out.println(board[i]);
        }
    }

    public static void recursive(int n, int x, int y, boolean dot) {

        if ( n == 1) {
            if ( dot ) {
                board[x][y] = '*';
            } else {
                board[x][y] = ' ';
            }
        } else if ( !dot ) {
            recursive(n/3, x, y, false);
            recursive(n/3, x + n/3, y, false);
            recursive(n/3, x + 2*n/3, y, false);
            recursive(n/3, x, y + n/3, false);
            recursive(n/3, x + n/3, y + n/3, false);
            recursive(n/3, x + 2*n/3, y + n/3, false);
            recursive(n/3, x, y + 2*n/3, false);
            recursive(n/3, x + n/3, y + 2*n/3, false);
            recursive(n/3, x + 2*n/3, y + 2*n/3, false);
        } else {
            recursive(n/3, x, y, true);
            recursive(n/3, x + n/3, y, true);
            recursive(n/3, x + 2*n/3, y, true);
            recursive(n/3, x, y + n/3, true);
            recursive(n/3, x + n/3, y + n/3, false);
            recursive(n/3, x + 2*n/3, y + n/3, true);
            recursive(n/3, x, y + 2*n/3, true);
            recursive(n/3, x + n/3, y + 2*n/3, true);
            recursive(n/3, x + 2*n/3, y + 2*n/3, true);
        }
    }
}

출력 시간이 오래걸리는 것 같아서 BufferedWriter를 사용했더니 통과한다.

package baekjoon;

import java.io.*;

public class Q2447 {
    static char[][] board;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(reader.readLine());

        board = new char[n][n];
        recursive(n, 0, 0, true);

        for (int i = 0; i < board.length; i++) {
            writer.write(board[i]);
            writer.write("\n");
        }
        writer.flush();
        writer.close();
    }

    public static void recursive(int n, int x, int y, boolean dot) {

        if ( n == 1) {
            if ( dot ) {
                board[x][y] = '*';
            } else {
                board[x][y] = ' ';
            }
        } else if ( !dot ) {
            recursive(n/3, x, y, false);
            recursive(n/3, x + n/3, y, false);
            recursive(n/3, x + 2*n/3, y, false);
            recursive(n/3, x, y + n/3, false);
            recursive(n/3, x + n/3, y + n/3, false);
            recursive(n/3, x + 2*n/3, y + n/3, false);
            recursive(n/3, x, y + 2*n/3, false);
            recursive(n/3, x + n/3, y + 2*n/3, false);
            recursive(n/3, x + 2*n/3, y + 2*n/3, false);
        } else {
            recursive(n/3, x, y, true);
            recursive(n/3, x + n/3, y, true);
            recursive(n/3, x + 2*n/3, y, true);
            recursive(n/3, x, y + n/3, true);
            recursive(n/3, x + n/3, y + n/3, false);
            recursive(n/3, x + 2*n/3, y + n/3, true);
            recursive(n/3, x, y + 2*n/3, true);
            recursive(n/3, x + n/3, y + 2*n/3, true);
            recursive(n/3, x + 2*n/3, y + 2*n/3, true);
        }
    }
}

recursive를 여러 갈래로 재귀 호출하는 부분을 반복문으로 만들면 더 깔끔할 것 같다.

public class Q2447 {
    static char[][] board;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(reader.readLine());

        board = new char[n][n];
        recursive(n, 0, 0, true);

        for (int i = 0; i < board.length; i++) {
            writer.write(board[i]);
            writer.write("\n");
        }
        writer.flush();
        writer.close();
    }

    public static void recursive(int n, int x, int y, boolean dot) {

        if ( n == 1) {
            if ( dot ) {
                board[x][y] = '*';
            } else {
                board[x][y] = ' ';
            }
        } else if ( !dot ) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    recursive(n/3, x + i*n/3, y + j*n/3, false);
                }
            }
        } else {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if ( i == 1 && j == 1 ) {
                        recursive(n/3, x + i*n/3, y + j*n/3, false);
                    } else {
                        recursive(n/3, x + i*n/3, y + j*n/3, true);
                    }
                }
            }
        }
    }
}

부녀회장 문제의 아파트때도 그렇고 테이블 같은 느낌의 풀이 과정이 필요할때는 2차원 배열을 빨리 생각해내면 좋을 것 같다.

11729 하노이 탑 이동 순서

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

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

public class Q11729 {

    static List<String> results = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(reader.readLine());

        recursiveTopMove(num,1, 3);
        writer.write(results.size()+"\n");

        for (String result : results) {
            writer.write(result+"\n");
        }
        writer.flush();
        writer.close();
    }

    private static void recursiveTopMove(int num, int from, int to) {
        int bridge = 6-from-to;

        if ( num != 1 ) {
            recursiveTopMove(num-1, from, bridge);
            print(from, to);
            recursiveTopMove(num-1, bridge, to);
        } else {
            print(from, to);
        }
    }

    private static void print(int from, int to) {
        results.add(String.valueOf(from)+" "+String.valueOf(to));
    }
}

이동 횟수를 더깔끔하게 할 수 없을까 고민중에 원판 수에 따라 규칙이 있다는 것을 알게 되었다.

최소 이동 횟수 = 2^원판수 - 1

위 식을 사용하면 따로 리스트를 만들지 않아도 된다.

import java.io.*;

public class Q11729 {

    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(reader.readLine());

        writer.write(((int) Math.pow(2, num) - 1) +"\n");
        recursiveTopMove(num,1, 3);

        writer.flush();
        writer.close();
    }

    private static void recursiveTopMove(int num, int from, int to) throws IOException {
        int bridge = 6-from-to;

        if ( num != 1 ) {
            recursiveTopMove(num-1, from, bridge);
            print(from, to);
            recursiveTopMove(num-1, bridge, to);
        } else {
            print(from, to);
        }
    }

    private static void print(int from, int to) throws IOException {
        writer.write(String.valueOf(from)+" "+String.valueOf(to)+"\n");
    }
}