[Summer/Winter Coding(2019)][시뮬레이션] 종이접기 - Java

문제 바로가기

코딩테스트 연습 - 종이접기

규칙을 찾아서 풀었씀니다.

class Solution {
    public int[] solution(int n) {
        if (n == 1) {
            int[] ret = { 0 };
            return ret;
        }

        int[] b = solution(n - 1);
        int[] a = new int[b.length * 2 + 1];

        System.arraycopy(b, 0, a, 0, b.length);
        a[b.length] = 0;
        int[] c = new int[b.length];

        for (int i = 0; i < c.length; i++) {
            if (b[b.length - 1 - i] == 1) c[i] = 0;
            else c[i] = 1;
        }

        System.arraycopy(c, 0, a, b.length + 1, c.length);
        return a;
    }
}

b: n-1일 때 정답이 들어갈 배열
a: n일 때 정답이 들어갈 배열. n-1일 때의 길이 * 2 + 1.
c: b배열을 반대로 뒤집었을 때 나오는 배열

n = 1 ❯ [0]
n = 2 ❯ [0 0 1]
n = 3 ❯ [0 0 1 0 0 1 1]
n = 4 ❯ [0 0 1 0 0 1 1 0 0 0 1 1 0 1 1]
...
n = i ❯ [i-1 0 ~(i-1)]

반으로 더 접었을 때, 중간에 0이 생기고 그 뒤에는 i-1의 역순이 됩니다.

0 0 1 0 0 1 1 -> 0 0 1 1 0 1 1

이런 규칙이 나오지여.

따라서 b를 이용해서 c를 구해주고 이를 a 뒤에다가 넣어주면 끝!

 

 

감사합니다!