[백준]11057 오르막 수 - 실버 1

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• DP, 구현

---

1. 문제설명

 

수를 오름차순 정렬할 때 오름차순이 유지되는 수의 갯수를 구하는 문제 입니다.

 

예를들어 수가 1자리인 경우 0 ~ 9 까지 총 10개의 수가 들어갈 수 있고 각각의 수는 그 자체로 오르막 수가 됩니다.

 

수가 2자리인 경우 00, 01, 02, 03, 04 이런식으로 00 ~ 09 까지 들어가고

1은 11, 12, 13 부터 19까지 10을 제외한 수가 오르막 수가 됩니다.

2도 마찬가지로 22부터 29까지 이런식으로 99까지 수가 올 수 있고 그 갯수가 55개 입니다.

 

이때 수의 길이 N이 주어질 때, 오르막 수의 개수를 구하는 프로그램을 작성하는 문제입니다. 출력은 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력해야 합니다.

---

[제한사항]

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

---

2. 접근방식

DP 문제의 기본은 점화식 입니다.

 

저번 시간에도 문제의 규칙성을 파악하고 일반화 하는 과정이 중요했는데 이번 문제 역시 손으로 그림을 그려가며 문제를 풀어보았습니다.

 

 

N 이 1인 경우 올 수 있는 숫자들은 0 부터 9까지 10개 존재합니다.

 

N 이 2인 경우 올 수 있는 숫자들은 00부터 09, 10 부터 19, 쭉 해서 99까지 55개 존재합니다.

 

이 N이 2인 경우 올 수 있는 숫자들을 전부 작성해보면 이렇게 생겼습니다.

 

11부터 시작하는 수는 10이 빠졌고

22부터 시작하는 수는 21과 20이 빠졌죠

33부터 시작하는 수는 거기에 32가 빠졌습니다.

 

이런식으로 이전수에 1개씩 더 빠져 00은 10개가 올 수 있으면 그 전 수들은 9,8,7,6,5 이런식으로 올 수 있는 수들이 달라집니다.

 

이걸 2차원 DP 테이블로 생각해 보았습니다.

 

 

이렇게 보면 규칙이 조금 보입니다.

 

N 이 2인 경우 0으로 시작할 때 올 수 있는 숫자의 개수는 0 부터 9까지 10개이고

1은 9개 2는 8개로 1개씩 작아지죠

 

전체 개수에 이전 개수를 빼준게 올 수 있는 숫자가 되는 것입니다. N 이 3인 경우도 작성해 보죠

 

더 확실하게 규칙이 보입니다.

 

이 부분을 채우기 위해서는 

 

이 합이 필요하고

 

이 부분은 이 합이 필요합니다.

 

즉 DP[i][j] 를 채우기 위해서는 DP[i - 1][j : ] 부분의 합과 같아집니다. 이를 코드로 세워 보겠습니다.

---

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())

# 2차원 DP 테이블 생성
DP = [[0] * 10 for _ in range(N + 1)] # 수를 맞춰주기 위해 N + 1 까지 생성

# DP 초기값 설정
for i in range(10):
    DP[1][i] = 1

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

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

---

[코드설명]

2차원 DP 테이블을 우선 생성해 주었습니다. 

DP 테이블의 인덱스 번호를 맞춰주기 위해서 N + 1 까지 생성해 주었고

오르막 수를 만들기 위해 존재 가능한 최대 자릿수는 10개 입니다.

 

따라서 2차원 DP 테이블을 다음과 같이 만들어 준 것입니다.

 

또한 N이 1인 경우 DP 테이블의 초기값은 모두 1이므로 위와 같은 반복문을 통해 초기값을 설정해 주었습니다.

 

그 후 2부터 N + 1 까지 자릿수를 맞춰 값을 채워줍니다.

DP[i][j] 는 앞선 점화식을 토대로 sum(DP[i - 1][j : ]) 로 구해줄 수 있으니 이를 이용해 DP 테이블을 채워주었습니다.

 

j가 1인 경우 DP[2][1] 은 DP[1][1 : ] 이 되죠 이 수는 

 

 

초록색 부분을 채우기 위한 노란색 범위와 동일 합니다.

 

j 가 2인 경우 DP[2][2] 는 DP[1][2 : ] 가 되고 이는 9를 제외한 나머지 수의 합이 DP[2][2]에 들어가는 것입니다.

 

이렇게 DP 테이블을 채우고 원하는 결과를 출력하기 위해 DP의 N 자리의 합을 10,007로 나눠 출력해 주었습니다.

---

4. 결과

---

[회고]

요번에 DP 실력을 키우기 위해 DP 문제를 풀어보고 있는데 항상 점화식을 세울때 고민이 많이 됩니다.

 

DP문제는 점화식을 얼마나 잘 세우느냐에 따라서 문제 해결 능력이 바뀌기 때문입니다.

 

이번 문제의 경우 이전 문제들은 1차원 DP 테이블을 이용하였는데 이번 문제는 2차원 DP 테이블을 활용하여서 조금 어려웠던 문제 같습니다.

 

그러나 손으로 모든 조건을 하나씩 구해보며 노트에 먼저 문제를 풀어보니 점화식을 제대로 세울 수 있었고 문제를 해결할 수 있었습니다.

 

DP 실력 향상을 위해 현재 제가 풀고 있는 문제들은 백준의 https://www.acmicpc.net/workbook/view/1984 이 문제집 입니다.

 

여기있는 문제들을 모두 풀 때까지 DP 문제를 계속 풀어보겠습니다.