프로그래머스: 종이접기

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/62049

프로그래머스

 문제설명 

 

n이 주어졌을때 종이를 n번 반으로 접으면 나오는 모양에서

위로 볼록하게 접혀있으면 0  아래로 볼록하게 접혀있으면 1 을 출력한다.

 

 알고리즘 

1 2 3 번째 결과까지보고 4번째꺼보면 규칙이 보이겠다싶어서 4번째꺼 접어봤다

규칙을 살펴보면

n번째 배열은  n-1번째 배열을 왼쪽부터 넣고 가운데에  0 을 넣고 반대쪽에는

n-1번째 배열을 역순으로 넣는데 1이면 0을넣고 0이면 1을 넣어주면된다.

예를 들면 n-1번째 배열이 0 0 1 1 이면 n번째 배열은 0 0 1 1 0 0 0 1 1 이런 느낌이다.

 

 

 코드 

 

#include<iostream>
#include<string>
#include<vector>
 
using namespace std;
 
vector<int>ans, b;
 
vector<int> func(int n) {
 
    //n=1 이면 0을 리턴
    if (n == 1) return { 0 };
    
    //왼쪽에는 n-1 번째 배열을 넣어줘야하므로 임시로 저장
    b = func(n - 1);
 
    //n-1 번째 배열을 먼저 넣어주고
    ans = b;
 
    //0을 넣어준다
    ans.push_back(0);
 
    //n-1번째 배열을 역순으로 넣는데 0이면 1, 1이면 0을  넣어준다.
    for (int i = b.size() - 1; i >= 0; i++) {
        int num = b[i];
        if (num == 0) ans.push_back(1);
        else ans.push_back(0);
    }
 
    return ans;
 
 
}
 
vector<int> solution(int n) {
    vector<int> answer = func(n);
    return answer;
}