[Algorithm] 11057. 오르막 수

11057: 오르막 수(DP)

11057 문제 보기

• 문제 티어 : S1
• 풀이 여부 : Failed
• 소요 시간 : 26:57

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
dp = [1 for _ in range(10)]

for i in range(1, N): # 1~N까지의 자릿 수
  for j in range(1, 10): # 0을 제외한 각 숫자에 대해 이전 숫자의 합을 더함
    dp[j] += dp[j-1] 

print(sum(dp) % 10007)

접근 방식

N(자릿수)이 증가함에 따라 0~9까지의 맨 뒷자리수가 N-1 자릿수의 결과를 가져와 사용한다.

→ 계산의 중복, 이전 값의 재활용 : DP로 접근해야 하는 문제

1. 길이 1부터 N까지의 자릿수 순회

   1. 길이에 상관 없이, 맨 뒷자리가 0인 수 중 오르막 수 조건에 일치하는 수는 오직 000… 1개 뿐

   → 1~9까지의 뒷자리수를 순회하며 값을 누적해 더해감

   b. DP테이블 갱신

잘못된 접근 방식(+ 코드)

# 접근 방식
# n개의 자리수의 인덱스를 일의자리부터 차례로 비교해 오르막 수가 아닌 경우를 발견할 때 플래그 표시 -> 완전탐색
# 각 자리에 올 수 있는 경우의 수: 0~9 - 10가지
# N의 최대 값: 1000 -> 나올 수 있는 최대 경우의 수 : 10^1000 -> 10^4
# 길이 N을 가진 수를 하나씩 순회 : 최대 길이 1000 -> 1000^1000 -> 10^6 

import sys
input = sys.stdin.readline

N = int(input())
ans = 0
arr = []
for i in range(10**N): # 나올 수 있는 경우의 수
  if len(str(i)) >= N:
    arr.append(str(i))
  if len(str(i)) < N:
    new_i = '0'*(N-len(str(i)))+str(i)
    arr.append(new_i)

for i in range(len(arr)): # 모든 경우의 수 순회
  asc_flag = True # 오르막 수 플래그
  for j in range(len(arr[i])-1): # 각 경우의 수의 자릿수 순회
    if arr[i][j] > arr[i][j+1]:
      asc_flag = False
  if asc_flag:
    print(arr[i])
    ans += 1

print(ans % 10007)

이런 유형의 문제는 DP로 접근해야 하는 문제라는걸 알고 있었지만, 점화식을 세우지 못해 처음엔 완전탐색으로 접근했었다.

1. 나올 수 있는 모든 경우의 수 뽑기
   • ex) N=3, 001도 길이가 3인 수가 됨
2. 모든 경우의 수를 순회하며, 각 자릿수 비교
   • 뒷자리 수가 더 크면 flag 갱신(True → False)
3. True인 경우만 ans 갱신

→ 메모리초과

배운점 또는 느낀점

DP는 점화식 생각하는게 제일 어려운 것 같다…

딱 봐도 DP문제 유형이면, 점화식 생각하기 어렵다고 완탐으로 돌릴 생각보다

작은 문제들의 솔루션이 큰 문제에 어떻게 사용되는지 관계를 파악하는데 시간 더 들이기!