[문제풀이] 종이접기

업데이트:

문제 링크 : 종이접기

풀이 시간 : 20분

1. 문제 풀이

규칙을 찾으면 간단한 문제

반으로 접을 때마다 기존의 접힌 구간(0 or 1) 사이에

0과 1을 번갈아 넣어주면 된다.

ex)

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

2. 소스 코드

    static public int[] solution(int n) {
		// 한번 접을 때마다 두배씩 증가
		int size = (int) Math.pow(2, n);
		int[] answer = new int[size - 1];
		// 0과 1을 넣어야 하므로 초기값은 -1로 세팅
		for (int i = 0; i < answer.length; i++) {
			answer[i] = -1;
		}
		// 처음에는 두칸씩 증가하면서 0과 1을 넣어준다
		int pivot = 2;
		for (int i = 0; i < size / 2; i++) {
			if (answer[i] == -1) {
				int num =0;
				for (int j = i; j < answer.length; j=j+pivot) {
					answer[j] = num;
					num = Math.abs(num-1);
				}
				// 간격을 점차 늘린다.
				pivot *=2;
			}
		}
		return answer;
	}

3. 후기

규칙을 찾지 못하면 풀 수 없는 문제인듯 하다

규칙을 금방 찾아서 특별한 알고리즘 없이 쉽게 풀었다.

참고