프로그래머스 : 종이접기 DP

https://programmers.co.kr/learn/courses/30/lessons/62049

코딩테스트 연습 - 종이접기 | 프로그래머스

#include <string>
#include <vector>

using namespace std;
//1번
// 0
//2번
//0(1번) 0 1
//3번
//001(2번) 0 011
// 4번 
// 001 0 011(3번) 0 0011011
//5번
// 001 0 011 0 0011011(4번) 0 반대
vector<vector<int>> a; 
vector<int> solution(int n) {
    vector<int> temp;
    temp.push_back(0);
    a.push_back(temp);
    
    for(int i=1; i<n; i++){
        vector<int> input ;
        temp = a[i-1];
        input = temp;
        input.push_back(0);
        int t_size= temp.size();
        for(int j=t_size-1; j>=0; j--){
            if(temp[j]==0){
                input.push_back(1);
            }else{
                input.push_back(0);
            }
        }
        
        a.push_back(input);
    }
    return a.back();
}

bottom - up dp 로 풀었다.

 

그런데 비트 마스크로도 풀수도 있을꺼같다. (X)

-> 비트가 int 는 32 bit , longlong 은 64 bit 이기때문에

점점 비트 수가 n*2+1 형식으로 증가해서 비트수가 넘어가서 비트 마스크로는 풀수 없다.

 

아래는 비트마스크로 풀어본거..

n 이 증가하면 못풀지만 n 이 작으면 풀리는 거니까 ... 적어놈,,

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>
using namespace std;

long long v[21][2];
// 1번 
// 1개
// 2번 3개 = 1*2 +1
// 3번 7개 = 3*2 +1
// 4번 15개 = 7*2+1

vector<int> solution(int n) {
    vector<int> answer;
    v[1][0] = 0;
    v[1][1] = 1;
    for(int i=2; i<=n; i++){
        long long now=v[i-1][0]; // 001
        long long next = 0;
        for(int j=0; j<v[i-1][1]; j++){
            next = next<<1;
            next|=now&1;
            now=now>>1;
        }
     
        long long temp = (((1<<v[i-1][1])-1)-next); // 1000 -1 --> 111 - 100 = 011
      
        v[i][0] = v[i-1][0]<<(v[i-1][1]+1) ; // 001 0 000
        v[i][0]|=temp; // 001 0 011
        v[i][1] = v[i-1][1]*2+1;
    }
    long long temp = v[n][0];
    for(long long i=0; i<v[n][1]; i++){
        answer.push_back(temp&1);
        temp>>=1;
    }

    reverse(answer.begin(),answer.end());
                    
    return answer;
}