#10844 쉬운 계단수

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

10844번: 쉬운 계단 수

실버 1의 문제이다. 문제는 굉장히 단순하지만 핵심 알고리즘을 떠올리기가 어려웠다. 원래 dp가 dfs/bfs보다 어려운게 맞나? 아무튼!

 

#include <iostream>
#include <algorithm>
#define MAX 1000000000
using namespace std;

long long dp[101][11];
long long cnt;

int main()
{
  //freopen("input.txt","r",stdin);
  int n;
  int l;
  cin>>n;
  for(int i=1;i<=9;i++){  
    dp[1][i]=1; 
  }

  for(int i=2;i<=n;i++){
    for(int j=0;j<10;j++){
      if(j==0){
        dp[i][j]=dp[i-1][j+1]%MAX;
      }
      else if(j==9){
        dp[i][j]=dp[i-1][j-1]%MAX;
      }
      else{
        dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%MAX; 
      }
    }
  }
  
  for(int i=0;i<=9;i++){
    cnt=cnt+dp[n][i];
  }
  cout<<cnt%MAX<<'\n';
}

핵심 아이디어는 2차원 배열을 사용하는것이었다. 마지막 수를 L이라고하고 길이가 N인 계단수를 저장할 배열을 dp라고 하였다.

마지막 수가 L이고 길이가 N인 계단수는 다음과 같다.

__ __ __ __ ... __ L  -> 길이가 N

이때 L전에는 L+1 과 L-1만이 올 수 있다. 따라서 이 문제는 부분문제로 쪼개질 수 있다!

__ __ __ __ ... L+1 OR L-1  -> 길이가 N-1

따라서 점화식을 세울 수 있다.

 

dp[N][L] = dp[N-1][L-1] + dp[N-1][L+1];

 

이렇게하고 답을 구하는 코드를 구현했었다. 물론 아직 미흡하다는 것은 알았기에 제출은 하지않고 테케를 돌려본 결과 다른 값이 나왔다. 생각을 해보니 마지막 수가 0일때, 9일때는 위의 점화식이 성립하지 않는다는것을 알게되었다.

 

따라서 끝 값을 고민해 보았다. 끝에 들어가는 값은 0과 9가 있다. 마지막 수가 0이라면 L-1은 음수가 되어 들어갈 수 없는 값이고, 마지막 수가 9라면 L+1 은 10이 되어 마찬가지로 들어갈 수 없다.

따라서 L==0 일때와 L==9 일때를 예외 처리 해주었다.

각각 L==0일때는 dp[N][L] = dp[N-1][L+1] 가 되고, L==9 일때는 dp[N][L] = dp[N-1][L-1] 가 된다.

이렇게 하고 당당하게 제출을 했더니 그냥 퍼센트 진행도 안되고 틀렸다. 이유가 뭘까 고민해보았는데 N이 100 정도로 큰 수가 된다면 뭔가 dp배열에 너무 큰 값이 들어갈 것 같았다. 그래서 넣어본 결과 그냥 무지성 어이없는 수가 나와서 재빨리 dp와 cnt를 long long으로 바꾸어주었다. 근데 그래도 틀렸다고 떴다. 배열에 심지어는 음수가 들어가는 경우도 있었다. 답답한 마음에 정답 코드를 보니, 10억으로 나누어주는 부분에서 내가 실수한 부분이 있었다.

 

문제에서 10억으로 나눈 나머지를 답으로 제출하라는 건 dp배열 계산 도중에 10억이 넘는 값이 나온다는 얘기이다. 따라서 dp를 계산해 줄 때마다 10억으로 나누어주었더니 정답처리가 되었다!