문제 링크

풀이

이 문제를 풀기 위해서 실제로 종이를 접어보았다...
20분정도 고민하다 보니 규칙이 보였다.

1번: 0
2번: 0 0 1 ==> [0 -> 1]
3번: 001 0 011 ==> [001 -> 011]
4번: 0010011 0 0011011 ==> [0010011 -> 0011011]
5번: 5: 00100110011011 0 00100111011011 ==> [00100110011011 -> 00100111011011]

1) 접히는 부분은 항상 0이다.
2) 접힌 후에는 접히기 이전의 부분이 밖으로 접히게 된다. (0이었던 중간값이 1로 변경)

이 문제를 구현하기 위해 DP 개념을 적용하였다.
DP란 결국 큰 문제를 작은 문제로 나누는 개념이다.
더 쉽게 이야기해서 다시 계산하지 않고 이전까지 계산된 값을 사용하여 다음 계산을 이어가는 것이다.

DP[n-1]번째 접은 단계까지 저장된 결과 + DP[n]번째 단계 실행 이후 결과 = Answer

코드

import java.util.*;
class Solution {
  public static int[] solution(int n) {
        if( n == 1 )
            return new int[] {0};

        List<Integer>[] DP = new ArrayList[n+1];
        DP[1] = new ArrayList<>(Arrays.asList(0));
        for (int i = 2; i <= n; i++) {
            List<Integer> temp = new ArrayList<>(DP[i-1]);
            temp.set(DP[i-1].size()/2, 1);

            DP[i] = new ArrayList<>(DP[i-1]);
            DP[i].add(0);
            DP[i].addAll(temp);
        }

        return toList(DP[n]);
    }

    private static int[] toList(List<Integer> list) {
        int[] ret = new int[list.size()];
        int i = 0;
        for( Integer value : list ) {
            ret[i++] = value;
        }
        return ret;
    }
}