[알고리즘] 백준 10844 c++

문제 링크

10844번: 쉬운 계단 수

틀린이유

사고 흐름

• N = 1

   1
    2
    …
    9
    => 9개
    

• N = 2

  10 12
   21 23
   …
   89 87
   98
   => (9-1)*2 + 1 = 17
   
   

• N = 3

  101 / 121 123
  210 212 / 232 234
  …
  898 / 876 878
  989 987
  => (17-2)*2 + 2 = 32

위와 같이 계단의 수를 셀 수 있다. 계단 수에서 문제가 되는 수는 끝자리 0과 9이다. 나머지 수는 2개씩 만들어지는데 얘네는 하나씩만 만들어지기 때문이다.

이렇게 끝자리 0과 9가 포인트라는 것은 발견했지만, 더 쉬운 방법을 찾기 위해 수식을 만들었다.

d[i] = 2*(d[i-1] - c[i-1]) + c[i-1];
c[i] = (c[i - 1] - 1) * 2 + 1;

N=5까지 확인했을 때는 맞았었는데, 틀렸습니다가 떴다. 즉 수식이 틀린 것이다.
그럼 이제 다시 돌아가 0과 9를 포인트로 잡고 이 숫자들을 따로 세는 방법을 생각했어야 했다.

문제 분석

문제

• ex) 45656
• 위와 같이 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다
• 구하는 거: 길이가 N인 계단 수가 총 몇 개인가?
• 단, 0으로 시작하는 수는 계단수가 아니다

입력

• 1 ≤ N ≤ 100

출력

• 정답을 1,000,000,000으로 나눈 나머지 출력

해결방안

끝자리 0과 9를 저장할 수 있는 방법으로는 어떤 게 있을까? 따로 배열을 둘까? 2차원 배열로 만들까?

끝자리 +- 1을 해서 계단수가 만들어진다. 그러면 끝자리를 2번째 열에 두어 저장하면 되겠다!

DP

1. 테이블 정의하기

   d[i][k] = 끝자리가 k이고 길이가 i인 계단수의 개수

2. 점화식 찾기

   for (int j=0; j≤9; j++) {
   	if (j ≠ 0) d[i][j] += d[i-1][j-1] // -1 했을 때
   	if (j ≠ 9) d[i][j] += d[i-1][j+1] // +1 했을 때
   }

3. 초기값 설정

   for (int i=1; i<=9; i++) d[1][i] = 1;
   

주의할 점

구하는 것은 길이가 N이고 마지막 자리가 k인 계단수가 아니라 길이가 N인 계단수이다. 따라서 길이가 N인 수에서 마지막 자리가 0~9까지 더해야한다.

앞서서 d[i][k]는 1,000,000,000로 나눠서 저장할 것이다. 이 값들을 더하려고 보니까, int의 범위는 21억이므로 10^9(10억)이 3개 이상만 되어도 int의 범위를 넘게 된다. 따라서 답을 더할 때 필요한 변수는 int가 아니라 long long으로 두어야한다.

코드

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

// d[i][k] = i자리이면서 끝자리가 k인 계단수의 개수
int d[102][10];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    // 초기값 설정
    for (int i=1; i<=9; i++) d[1][i] = 1;

    for (int i=2; i<=N; i++){
        for (int j= 0; j<=9; j++){
            if (j != 0) d[i][j] += d[i-1][j-1];
            if (j != 9) d[i][j] += d[i-1][j+1];
            d[i][j] %= mod;
        }
    }

    long long ans = 0;
    for (int i=0; i<=9; i++) ans += d[N][i];
    cout << ans % mod;

    return 0;
}