알고리즘

[백준]10844 쉬운 계단 수 - 실버 1

swanzzz 2025. 5. 14. 22:35
반응형

[오늘의 문제]

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

[오늘의 학습 키워드]

  • DP, 구현

1. 문제설명

 

쉬운 계단 수란 양 옆으로 1씩 차이나는 수를 의미합니다.

그런데 0 으로 시작하는 수는 계단수가 아닙니다.

 

N이 주어질 때 계단수를 확인하여 그 계단 수를 1000000000 으로 나눈 값을 출력하는 문제입니다.

[제한사항]

  • 시간 제한 1초
  • 메모리 제한 256MB
  • 1 ≤ N ≤ 100

2. 접근방식

3번째 DP 문제입니다.

 

DP 문제는 점화식을 세워야 하는데 점화식은 곧 문제의 패턴을 찾는 방법 입니다.

 

이번 문제의 경우 예제가 2개 주어져 있습니다.

 

1이 들어온 경우 계단 수는 9개가 존재하고

2가 들어온 경우 계단 수는 17개가 존재합니다.

 

이 두 수를 이용해서 DP 테이블을 채우는 점화식을 세워 보겠습니다.

 

N 이 1인 경우 0을 제외한 1부터 9까지 계단수 자기 자신 9개가 존재합니다.

 

N 이 2가 주어진 경우 계단수는 10, 12 / 21, 23 / 32, 34 / 43, 45 / 54, 56 / 65, 67 / 76, 78 / 87, 89 / 98

 

자세히 보면 1이 가질 수 있는 계단 수는 0과 2 뿐이고

 

2가 가질 수 있는 계단 수는 1 과 3 뿐입니다.

 

즉, 자기 자신을 제외한 -1, +1 이 계단수가 되는 것이죠 

 

그렇다면 N 이 2가 주어졌을 때 계단 수를 채우기 위해서는 1로 시작할 때 올 수 있는 숫자의 개수는 2개

2도 2개, 3도 2개 ... 9는 뒷 수가 없으니 1개가 옵니다.

이를 테이블을 이용해 채워보면 다음과 같습니다.

 

이런식으로 채워지게 되는데 앞서 설명한 대로 자기 자신을 제외한 -1, +1 수의 개수를 이용해 현재 칸을 채우면 아래 그림과 같이  채워지게 되는 것입니다.

 

0의 경우도 마찬가지 겠죠 그러나 0으로 시작하는 수는 계단 수가 아니기 때문에 패턴을 찾기 위한 편의상 0을 이용해 주었고 실제는 1부터 시작 하겠죠

 

위 그림을 코드로 점화식을 세워 보면 다음과 같습니다.

 

DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1]

 

현재 수의 -1 이 되는 계단 수의 개수 + +1 이 되는 계단 수의 개수의 합이 현재 위치의 계단 수가 되겠죠

 

여기서 주의할 점은 0과 9의 경우 계단 수를 채우기 위해 -1 수와 + 1 수를 확인할 때 indexError가 발생할 수 있다는 것이겠죠 이를 유의하며 코드를 작성해 보았습니다.

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())

# DP 테이블 설정
DP = [[0] * 12 for _ in range(N + 1)]

# 초기값 입력
for i in range(2, 11):
    DP[1][i] = 1

# 점화식 토대로 값 채우기
for i in range(2, N + 1):
    for j in range(1, 11):
        DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1]

# 출력
print(sum(DP[N]) % 1000000000)

[코드설명]

DP 테이블을 생성할 때 0과 9 양 옆에 패딩값을 주기 위해 빈 배열을 넣은 크기로 생성해 주었습니다.

 

그러면 이런 형태로 DP 테이블이 생성 되겠죠

여기에 N 이 1인 경우 초기값을 넣어줍니다.

 

초기값은 모두 1 이고 0을 제외한 1부터 9까지 1로 채워 줍니다.

 

N이 2가 들어는 순간 부터 점화식을 이용해 값을 채워 줍니다.

 

그러기 위해 i는 2부터 N + 1 까지 탐색을 실시하고 j는 1부터 11까지 탐색하여 탐색 범위를 맞춰 줍니다.

 

여기서 1부터 11까지 탐색하니 1이 0에 해당하고 10이 9에 해당하겠죠

 

앞에 패딩값으로 빈 칸을 생성해 주었으니 indexError를 걱정하지 않고 점화식을 토대로 값을 채워 줍니다.

 

앞서 찾은 규칙을 토대로 점화식을 세웠고 값을 채워주게 되면 DP 테이블은 다음과 같이 생성 됩니다.

 

 

이렇게 생성된 DP 테이블에서 원하는 수만 골라 1000000000 으로 나눈 나머지 값을 출력해 주면 됩니다.

4. 결과

[회고]

 

이번 문제의 경우 점화식을 세우며 패턴을 금방 찾았었는데, 막 찾은 패턴을 토대로 값을 채우다 보니 N이 3이 입력되는 순간 갯수가 달라 졌었습니다.

 

아무래도 0을 제외한 수를 고려해 값을 채우려다 보니 코드가 복잡해졌었고 초기에 세웠던 점화식은 손코딩한 코드 처럼

 

i == 2가 오고 j == 1이 온 경우 기존의 범위에 1을 더한 값을 넣고 continue로 아랫줄을 뛰어넘었습니다.

 

이렇게 코드를 짜니 3이 들어간 경우 31이 출력되었고 1%에서 틀렸습니다.

 

좀더 패턴을 단순화 시키기 위해 고민 하다가 0의 범위도 포함하여 그냥 값을 구하면 더 편할것 같았고 indexError를 방지하기 위해 앞에 패딩값만 넣어주면 되겠는데? 라는 생각으로 DP 테이블의 범위를 늘려주고 점화식을 단순화 하였습니다.

 

그 결과 금방 코드를 수정해 문제를 해결할 수 있었습니다.

 

DP 문제를 계속해서 풀며 점화식을 세우는 실력?이 점점 좋아지고 있는 것 같습니다.

 

확실 문제를 보고 손으로 코딩해보며 일일이 점화식을 세워보니 확실히 실력이 많이 는것 같습니다.

 

이 풀이를 보는 사람이 있을지는 모르지만 손코딩은 많은 도움이 되니 꼭 손으로 먼저 풀고 코드로 풀어보시기를 권장드립니다.

반응형