2025/02/05 백준 1562 계단수

난이도: G1

알고리즘: dp

 

https://www.acmicpc.net/problem/1562

 

1. 문제 탐색

 

제한 시간: 2초, 메모리 제한: 128MB

 

완전탐색으로 풀기엔 시간이 너무 많이 걸릴 것 같았다. 한 자리당 0~9까지 넣을 수 있고, 총 100자리까지 가능하기 때문에 10^100이나 걸리기 때문이다.

 

dp로 이전 것을 활용해서 풀어야 시간이 절약된다.

 

 

2. 코드 설계하기

 

dp[i][j]라고 하고, 이것을 길이가 i이고 끝자리가 j인 계단수라고 한다면

i-1 길이의 계단수의 끝자리에 따라 3가지 경우가 있다.

1. i-1 길이의 계단수의 끝자리가 0인 경우: i 길이의 계단수의 끝자리는 1만 가능하다.

2. i-1 길이의 계단수의 끝자리가 9인 경우: i 길이의 계단수의 끝자리는 8만 가능하다.

3. i-1 길이의 계단수의 끝자리가 1~8인 경우: i 길이의 계단수의 끝자리는 i-1길이의 계단수의 끝자리+1, -1 가능하다.

 

*0~9까지 모든 수를 사용했는지 확인하는데 시간을 적게 쓰기 위해 비트마스킹 방법을 사용한다.

(챌린지 해설지 참고함. - 근데 감이 잘 안와서 나중에 다시 적을 예정)

 

3. 시도회차별 수정 사항

해설지 보고 참고하여 코드 작성해서 한번에 통과했다.

 

4. 정답코드

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    long long answer = 0;
    vector<vector<vector<long long>>> dp(101, vector<vector<long long>>(10,vector<long long>(1<<10, 0))); 
    
    //dp[i][j][k]: 길이가 i인 계단수 중에 끝자리가 j인 경우의 수 중 현재까지 방문한 수를 비트로 변환한 값이 k인 경우의 수
    //길이가 1인 계단수: (1), (2), (3), (4), (5), (6), (7), (8), (9) (0은 X)
    //비트마스킹
    for(int j=1; j<=9; j++)
    {
        dp[1][j][1<<j] = 1;
    }

    for(int i=2; i<=100; i++)
    {
        for(int j=0; j<=9; j++)
        {
            for(int k=0; k<(1<<10); k++)
            {
                if (j-1 >= 0)
                    dp[i][j][k | (1 << j)] += dp[i-1][j-1][k]; //k | (1 << j)
                if (j+1 <= 9)
                    dp[i][j][k | (1 << j)] += dp[i-1][j+1][k];
                dp[i][j][k | (1 << j)] %= 1000000000;
            }
        }
    }

    cin>>n;

    for(int j=0; j<=9; j++)
    {
        answer += dp[n][j][1023];
        answer %= 1000000000;
    }

    cout<<answer;
}