[BOJ/백준][Gold4] 2698 : 인접한 비트의 개수 (C++)

www.acmicpc.net/problem/2698

2698번: 인접한 비트의 개수

 

 

[난이도] Gold4

[유형] DP

 

[풀이]

dp[n][k][f] : 첫 자리가 f로 시작하면서 크기가 n이면서 비트의 개수가 k인
수열의 개수.
f==1 : dp[n][k][f] = dp[n-1][k][0]+dp[n-1][k-1][1] (첫 자리수가 1이므로
n-1크기의 수열도 1 로 시작하면 k를 1개 줄일 수 있다.)
f==0 : dp[n][k][f] = dp[n-1][k][1]+dp[n-1][k][0]

종료조건은 n이 1씩 감소하는게 보장되므로 n==2인 경우로 처리한다.

#include <cstdio>
#include <cstring>
using namespace std;
int tc,N,K,dp[102][101][2];
int sol(int n,int k,int f){
    if(k<0) return 0;
    if(n==2){
        if(f==1) {
            if(k<2) return 1;
        }else{
            if(k==0) return 2;
        }
        return 0;
    }
    int& ret = dp[n][k][f];
    if(ret!=-1) return ret;
    ret = 0;
    if(f==0) ret += sol(n-1,k,1)+sol(n-1,k,0); 
    else ret += sol(n-1,k-1,1)+sol(n-1,k,0);
    return ret;
}

int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d",&N,&K);
        memset(dp,-1,sizeof(dp));
        printf("%d\n",sol(N+1,K,0));
    }
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2698.cpp