백준 20187번 - 종이접기(java)

💡 문제 

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

 

💡 아이디어

결론부터 말하자면, 나도 맞아서 놀란 문제. 골드3인데 너무 단순하게 풀어버렸다.

 

일단 이 문제에 대한 블로그가 많지는 않지만, 모두 시뮬레이션으로 문제를 해결한듯 했다.

그러나 나는 시뮬레이션을 사용하지 않았다.

 

이 문제를 풀기 전 아래 2가지를 전제로 하였다. (왜냐고 물어본다면.. 설명할 자신이 없다. 그냥 그림을 그리다 보니 그렇구나 싶었다.)

전제1) 중간 과정은 상관 없고 결국 마지막 가로 접기 방향과 마지막 세로 접기 방향으로 구멍 모양이 결정된다.

 

전제1에 의해 접는 방식은 결국 총 4가지 경우로 귀결된다.

1. 왼쪽 위로 마지막으로 접은 경우

2. 오른쪽 위로 마지막으로 접은 경우

3. 왼쪽 아래로 마지막으로 접은 경우

4. 오른쪽 아래로 마지막으로 접은 경우

 

 

전제2) 결국 k의 크기가 얼마나 크던지 2x2의 구멍 모양이 반복된다.

k=3, 구멍 위치=0, 마지막에 왼쪽 위에서 끝나는 경우

 

 

전제2에 의해 결국 2x2의 구멍 4개 위치만 구하면 된다. 

우선 각 경우에서 2x2의 왼쪽 위 구멍 위치(코드 상에서 one이라는 변수)를 구했다.

1번 경우는 원래 왼쪽 위로 끝났으므로 유지,

2번 경우는 오른쪽 위에서 끝났으므로 2x2의 왼쪽 위 구멍은 세로 대칭

3번 경우는 왼쪽 아래에서 끝났으므로 2x2의 왼쪽 위 구멍은 가로 대칭

4번 경우는 오른쪽 아래에서 끝났으므로 2x2의 왼쪽 위 구멍은 가로&세로 대칭

 

one을 구했으면 two는 one의 세로 대칭, three는 one의 가로 대칭, four는 one의 가로&세로 대칭만 하면 바로 구할 수 있다.

 

 

이제 다 구했다. 그냥 k의 크기만큼 one, two, three, four를 반복 출력하면 된다.

 

💡코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_G3_20187_종이접기 {
    static int k;
    static int holeNum; //구멍 뚫는 위치
    static char lastHor, lastVer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 2 * k; i++) {
            char fold = st.nextToken().charAt(0);
            if (fold == 'D' || fold == 'U') {
                lastHor = fold; //마지막 가로 접기
            } else {
                lastVer = fold; //마지막 세로 접기
            }
        }

        holeNum = Integer.parseInt(br.readLine());

        // 2x2에서의 왼쪽 위 위치로 구멍 위치 변경
        if (lastVer == 'L' && lastHor == 'U') { //1. 왼쪽 위로 마지막으로 접힌 경우
            holeNum = holeNum;
        }
        if (lastVer == 'R' && lastHor == 'U') { //2. 오른쪽 위로 마지막으로 접힌 경우
            holeNum = ver(holeNum);
        }
        if (lastVer == 'L' && lastHor == 'D') { //3. 왼쪽 아래로 마지막으로 접힌 경우
            holeNum = hor(holeNum);
        }
        if (lastVer == 'R' && lastHor == 'D') { //4. 오른쪽 아래로 마지막으로 접힌 경우
            holeNum = hor(ver(holeNum));
        }

        int one = holeNum; // 2x2에서의 왼쪽 위 위치
        int two = ver(holeNum); // 2x2에서의 오른쪽 위 위치
        int three = hor(holeNum); // 2x2에서의 왼쪽 아래 위치
        int four = hor(ver(holeNum)); // 2x2에서의 오른쪽 아래 위치

        //결국에는 2x2 구멍 4개의 반복
        for (int i = 0; i < Math.pow(2, k); i++) {
            if (i % 2 == 0) {
                for (int j = 0; j < Math.pow(2, k - 1); j++) {
                    System.out.print(one + " ");
                    System.out.print(two + " ");
                }
                System.out.println();
            } else {
                for (int j = 0; j < Math.pow(2, k - 1); j++) {
                    System.out.print(three + " ");
                    System.out.print(four + " ");
                }
                System.out.println();
            }
        }
    }

    //세로 대칭 구멍 위치
    private static int ver(int holeNum) {
        if (holeNum == 0) return 1;
        if (holeNum == 1) return 0;
        if (holeNum == 2) return 3;
        return 2;
    }

    //가로 대칭 구멍 위치
    private static int hor(int holeNum) {
        if (holeNum == 0) return 2;
        if (holeNum == 1) return 3;
        if (holeNum == 2) return 0;
        return 1;
    }
}

---

맞긴 했지만, 저 전제 2개가 맞았기 때문에 가능했던 것이고, 가장 안전한 건 시뮬레이션을 돌리는 것 같다!!