[코딩테스트] 2019 Winter Coding 2번 문제

문제

직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n=2인 경우의 예시입니다.

 

먼저 오른쪽 절반을 왼쪽으로 접습니다.

 

다시 오른쪽 절반을 왼쪽으로 접습니다.

 

 

종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 아래 그림과 같이 종이에 접은 흔적이 생기게 됩니다.

 

 

위 그림에서 V모양이 생긴 부분은 점선(0)으로, ^ 모양이 생긴 부분은 실선(1)으로 표시했습니다.

 

종이를 접은 횟수 n이 매개변수로 주어질 때, 종이를 절반 씩 n번 저은 후 모두 펼쳤을 때 생기는 접힌 부분의 모양을 배열에 담아 return하도록 solution 함수를 완성해주세요.

 

제한사항

종이를 접는 횟수 n은 1이상 20이하의 자연수입니다.

종이를 접었다 편 후 생긴 굴곡이 V모양이면 0, ^모양이면 1로 나타냅니다.

가장 왼쪽의 굴곡 모양부터 순서대로 배열에 담아 return해주세요.

---

접근 방법

주어진 입출력 예를 보고 단순히 n-1번째 패턴이 두 번 반복되고 1이 나오는 것인가 생각했습니다. 확인을 위해 직접 종이를 접어 n=4일때의 결과를 구해봤습니다. 그러나 생각과는 다른 결과가 나왔고, 다른 규칙을 찾았습니다. 찾은 규칙은 아래와 같습니다. 

n	결과
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

 

solution(n) = solution(n-1) + 0 + solution(n-1)의 가운데 항을 1로 바꾼 배열

---

풀이 (Java)

import java.util.*;

public class Solution{
	
	private static ArrayList<Integer> recur(int num){
		ArrayList<Integer> arrayList = new ArrayList<>();
		ArrayList<Integer> left = new ArrayList<>();
		ArrayList<Integer> right = new ArrayList<>();
		
		if(num < 2){
			arrayList.add(0);
			return arrayList;
		}else{
			left.addAll(recur(num-1));
			right.addAll(left);
			right.set((left.size()/2),1);
			arrayList.addAll(left);
			arrayList.add(0);
			arrayList.addAll(right);
			return arrayList;
		}
	}
	
	private static int[] solution(int num){
		ArrayList answer_list = recur(num);
		int[] answer = new int[answer_list.size()];
		for(int i=0; i<answer.length; i++){
			answer[i] = (int) answer_list.get(i);
		}
		return answer;
	}
	
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();
		System.out.println(Arrays.toString(solution(a)));
	}
}