[백준][C++]10844번 쉬운 계단 수

문제

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

10844번: 쉬운 계단 수

 

 

풀이

• D[N][H] : 길이가 N인 계단에서 H 높이로 종료되는 계단 수를 만들 수 있는 경우의 수

  - (H = 0) D[i][H] = D[i - 1][H + 1]

  - (H = 9) D[i][H] = D[i - 1][H - 1]

  - (H = 1 ~ 8) D[i][H] = D[i - 1][H - 1] + D[i - 1][H + 1]

 

동적 계획법(Dynamic Programming) 알고리즘

동적 계획법(Dynamic Programming) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;

  vector<vector<long>> count(N + 1, vector<long> (10, 0));
  // 0으로 숫자가 시작할 수 없으므로 D[0][1]은 0으로 초기화
  for(int i = 1; i <= 9; i++)
  {
    count[1][i] = 1;
  }

  for(int i = 2; i <= N; i++)
  {
    count[i][0] = count[i - 1][1];  // N에서 높이가 0이면 N - 1에서는 높이가 1이어야 계단 수가 가능
    count[i][9] = count[i - 1][8];  // N에서 높이가 9이면 N - 1에서는 높이가 8이어야 계단 수가 가능
    
    // 높이가 1 ~ 8이면서 N - 1에서 자신보다 한 단계 위 또는 한 단계 아래 높이에서 올 수 있음
    for(int j = 1; j <= 8; j++)
    {
      count[i][j] = (count[i - 1][j - 1] + count[i - 1][j + 1]) % 1000000000;  // 나온 결과를 1000000000 나머지 연산 수행하기
    }
  }

  long result = 0;
  for(int i = 0; i <= 9; i++)
  {
    result = (result + count[N][i]) % 1000000000;  // 정답값을 더할 때도 % 연산 수행
  }
  
  cout << result;  // result 출력하기
  
  return 0;
}