1562번 : 계단 수 [C++]

문제 링크

성공 여부(걸린 시간): 실패(30분)

참고한 블로그

아이디어

처음에 다행히 접근을 비슷하게 했다.

직전의 숫자에 +1, -1에 대한
그러나 방문 처리를 어떻게 해주어야 할지에 대한 감이 안와서
고전하다가 목표했던 30분에 도달해서 풀이를 보기로 했다.

 

아니라 다를까 내가 굳이 필요있겠나? 싶었던 비트마스킹을 통해 방문처리를 하는 것을 확인하고
이번 기회에 습득해보기로 했다.

 

우선 재귀 함수는 이와 같다.

int get_dp(int n, int before, int visited) {
    //종료 규칙 N-1부터 시작해서 0까지 0~9 숫자 전부 방문했는지 visited 체크 후 1 또는 0 return
    if (n == 0) {
        // 1을 return 하는 것은 해당 숫자가 계단수라는 말
        return visited == bit_max;
    }

    //해당 값을 계산했었다면 그냥 해당 값을 바로 return 해줌
    if (dp[n][before][visited]!=-1) {
        return dp[n][before][visited];
    }

    int sum = 0;

    //위 아래 숫자로 가능하다면 재귀를 통해 sum에 추가 
    if (before - 1 >= 0) {
        sum = (sum + get_dp(n - 1, before - 1, visited | (1 << before-1))) % MOD;
    }
    if (before + 1 < 10) {
        sum = (sum + get_dp(n - 1, before + 1, visited | (1 << before+1))) % MOD;
    }

    dp[n][before][visited] = sum;

    //결국 return 받게 되는 계단수의 개수
    return sum;
}

 

N-1부터 시작해서 0으로 도달했을때 종료되며 호출 함수에 해당 숫자가 계단 수인지에대한 여부(1)를 return한다.
bit_max가 뭐냐면 0~9자리니까 총 10개의 숫자를 전부 방문해야 하니까 이진수로는 11 1111 1111

16진수로 변경하면 0x3FF이므로 조건을 만족하는지 손쉽게 검사할 수 있다.

 

그리고 만약 이미 계산된 값은 바로 return해주고

 

아니라면 그 다음 숫자 2가지의 경우(현재 숫자 + 1, 현재 숫자 - 1)에 대해서 재귀를 호출해준다.

 

그리고 마지막에서는 취합된 계단 수의 갯수를 저장해주고 return 해준다.

정답 코드

#include <iostream>
#include <vector>
#include <cstring>
#define MOD 1000000000
using namespace std;

int dp[101][10][0x400];
int bit_max = 0x3FF;

int get_dp(int n, int before, int visit);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;

    //dp 배열값을 전부 -1로 초기화 해줌
    memset(dp, -1, sizeof(dp));

    int sum = 0;

    // 0~ N-1로 가는 방법도 가능하지만 
    // 그렇기 위해서는 N을 재귀함수인 get_dp에서도 인식할 수 있게
    // 전역으로 선언하거나 인자로 넣어줘야 하기에 N-1~0 이 방법이 더 좋은듯
    for (int i = 1; i <= 9; i++) {
        sum = (sum + get_dp(N - 1, i, (1<<i))) % MOD;
    }

    cout << sum;

    return 0;
}
int get_dp(int n, int before, int visited) {
    //종료 규칙 N-1부터 시작해서 0까지 0~9 숫자 전부 방문했는지 visited 체크 후 1 또는 0 return
    if (n == 0) {
        // 1을 return 하는 것은 해당 숫자가 계단수라는 말
        return visited == bit_max;
    }

    //해당 값을 계산했었다면 그냥 해당 값을 바로 return 해줌
    if (dp[n][before][visited]!=-1) {
        return dp[n][before][visited];
    }

    int sum = 0;

    //위 아래 숫자로 가능하다면 재귀를 통해 sum에 추가 
    if (before - 1 >= 0) {
        sum = (sum + get_dp(n - 1, before - 1, visited | (1 << before-1))) % MOD;
    }
    if (before + 1 < 10) {
        sum = (sum + get_dp(n - 1, before + 1, visited | (1 << before+1))) % MOD;
    }

    dp[n][before][visited] = sum;

    //결국 return 받게 되는 계단수의 개수
    return sum;
}