[프로그래머스] 종이접기 - Java

https://programmers.co.kr/learn/courses/30/lessons/62049

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

규칙찾는 문제 꿀잼!

 

n	result
1	0
2	0,0,1
3	0,0,1,0,0,1,1
4	0,0,1,0,0,1,1,0,0,0,1,1,0,1,1

일단 result를 보면 중앙의 0을 기준으로 우측 숫자들은 좌측 숫자를 대칭시킨 후 0=>1, 1=>0으로 바꾼 것이다.

그리고 좌측 숫자는 n-1일 때의 result와 동일하다.

 

이를 이용해서 코드를 짜면 된다.

 

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[(int) (Math.pow(2, n) - 1)];

        for (int i = 2; i <= n; i++) {
            int mid = (int) Math.pow(2, i - 1) - 1;

            for (int j = 1; j <= mid; j++) {
                answer[mid + j] = (answer[mid-j] + 1) % 2;
            }
        }

        return answer;
    }
}