[프로그래머스] 종이접기 Summer/Winter Coding(2019)

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

종이를 같은 방향으로 n번 접었다 펼쳤을 때 생기는 굴곡이 v 모양이면 0, ∧ 모양이면 1을 출력해야 한다.

규칙을 찾기 위해 종이를 직접 5번까지 접어보니 패턴이 나왔다.

​

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

5 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1

... ...

​

색으로 표시한 부분을 보면 N-1의 결과가 N의 파란 부분이 되고

중간의 0을 기준으로 빨간 부분과 대칭을 이루고 있다는 것을 알 수 있다.

​

따라서 배열을 만들어 2부터 n까지 차근차근 구해 값을 집어넣고 문제가 원하는 answer 벡터에 할당해주면 끝

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int arr[1111111] = { 0 };

vector<int> solution(int n) {
	vector<int> answer;
	for (int i = 2; i <= n; i++) {
		int a = 0;
		for (int j = pow(2, i) - 2; j >= pow(2, i - 1); j--) {
			if (arr[a] == 0)arr[j] = 1;
			a++;
		}
	}
	for (int i = 0; i<pow(2, n) - 1; i++) answer.push_back(arr[i]);

	return answer;
}