[BOJ 2698] 인접한 비트의 개수

문제 : https://www.acmicpc.net/problem/2698

아직 내공이 부족해서 한참 고민하고 겨우겨우 풀이한 문제였다.

핵심은 끝자리가 0일때와 1일때를 나누어 생각하는 것이고 n번째를 구하기 위해 n-1번째 값을 사용하기 위해 생각해 본 결과 점화식을 얻을 수 있었다. 또 점화식을 얻는데 중요한 힌트가 되었던 것은 문제 내에 식이 써있는 것도 많은 도움이 되었다.

dp[n][k][0] = dp[n-1][k][0] + dp[n-1][k][1]

dp[n][k][1] = dp[n-1][k][0] + dp[n-1][k-1][1]

소스코드

// //  main.cpp //  Algorihm // //  Created by sw on 2018. 9. 10.. //  Copyright © 2018년 sw. All rights reserved. // #include <cstdio> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #define MAX 101 using namespace std; int n,k; int dp[MAX][MAX][2]; queue<int> q; void solve(int n, int k){     dp[1][0][0]=dp[1][0][1]=1;     for(int i=2;i<=n;i++){         for(int j=0;j<i;j++){             dp[i][j][0] = dp[i-1][j][0]+dp[i-1][j][1];             dp[i][j][1] = dp[i-1][j][0]+dp[i-1][j-1][1];         }     }     q.push(dp[n][k][0]+dp[n][k][1]); } int main(int argc, const char * argv[]) {     int tc;     scanf("%d",&tc);     while(tc--){         scanf("%d %d", &n, &k);         memset(dp,0,sizeof(dp));         solve(n,k);     }     //출력     while(!q.empty()){         cout<<q.front()<<endl;         q.pop();     }     return 0; }