백준 2698번 인접한 비트의 개수

문제 링크입니다: https://www.acmicpc.net/problem/2698

문제에 공식이 제공되었기 때문에 매우 쉬운 DP 문제였습니다.

주의할 점은 s1이 0으로 시작할 수도 있고 1로도 시작할 수도 있기 때문에 두 경우의 수를 모두 더해줘야한다는 점입니다!

#include <iostream>

#include <cstring>

using namespace std;

 

const int MAX = 100 + 1;

 

int N, K;

int cache[MAX][MAX][2]; //N, K, 0 or 1

 

int numOfSequence(int len, int total, int bit)

{

        //기저 사례

        if (len >= N || total > K)

                 return 0;

        //조건 충족

        if (len == N - 1 && total == K)

                 return 1;

 

        int &result = cache[len][total][bit];

        if (result != -1)

                 return result;

 

        //다음 비트는 0일 수도 1일 수도 있다

        result = numOfSequence(len + 1, total, 0) + numOfSequence(len + 1, total + bit * 1, 1);

        return result;

}

 

int main(void)

{

        int T;

        cin >> T;

 

        for (int i = 0; i < T; i++)

        {

                 cin >> N >> K;

 

                 memset(cache, -1, sizeof(cache));

 

                 //s1=0 or 1

                 cout << numOfSequence(0, 0, 0) + numOfSequence(0, 0, 1) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~