오늘의 문제 - boj-11057

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

풀이

1. 테이블 정의하기

• dp[i][j] = 길이가 i고 끝이 j인 오르막수의 개수

2. 점화식 찾기

• dp[1] 일때 오르막수는 0 ~ 10까지로 10개를 갯수로 가진다.
  • 이때 마지막 수를 중심으로 0부터 9까지 테이블을 정리하면
    dp[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    이러한 형태로 이루어진다는 것을 알 수 있다.
• dp[2]부터는 dp[1]의 마지막 수 보다 큰 수들을 넣을 수밖에 없기 때문에 이제부터는 계산이 필요하다.
• dp[2][0]을 들여다보면 0으로 끝난 수에 올 수 있는 수는 0밖에 없다. 따라서 1을 갖게 된다. 수가 계속 증가해서 i까지 간다고 해도 dp[i][0]는 1을 값으로 갖는다.
• 이제 dp[2][1]을 살펴보면 가질 수 있는 수는 01 11 이 두가지이다. dp[1]에서 0으로 끝나는 수 + 1 , 1로 끝나는 수 +1 형태로 이루어진다는 것을 알 수 있다
• 마찬가지로 dp[2][2] 는 02 12 22 이렇게 세개의 수이고 동일한 형태를 띈다.
• 여기서 점화식을 유추해볼 수 있는데 dp[2][i]는 dp[1][0] + dp[1][1] + dp[1][2] ... dp[1][i] 형태로 이루어지므로
• 이 식을 반복문으로 일일이 더해줄 수도 있겠지만 동일한 형태가 반복되고 dp[2][i-1]에 이미 dp[1][1] + ...+ dp[1][i-1] 형태가 만들어져 있다.
• 이에 더해 dp[1][i] 값만 더해주면 되기 때문에 점화식은 다음과 같다.
• dp[i][j] = dp[i][j-1] + dp[i-1][j]

3.초기값 설정하기
점화식을 구하면서 언급한 바와 같이 dp[1]의 모든 값은 1로 초기화 해줄 필요가 있다.
그리고 dp[i][0]값은 언제나 1이기 때문에 1로 초기화가 필요하다.
이를통해 dp테이블을 처음부터 1로 초기화를하면 된다는 사실을 알 수 있다.

N = int(input())

dp = [[1] * 10 for _ in range(1001)]


for i in range(2, N+1):
    for j in range(1, 10):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) 
print(sum(dp[N])% 10007)

피드백

나에게 dp문제에서 제일 어려운 점을 꼽으라면 수학적사고를 통한 점화식 도출을 꼽을 수 있을 것 같다. 유튜브나 책을 찾아보아도 dp는 많은 문제를 접해보는 것이 좋다고 하는데 아직 많이 부족한가보다.
(이제까지 문제를 접한 방식이 너무 주먹구구식이었던것도 있지만)

그래도 긍정적인 부분은 문제를 봤을 때 dp문제라는 걸 이제는 직감할 수 있고 이 접근방식이 나에게 꽤 잘 맞는다고 생각했다. 1, 2, 3번을 따라서 생각을 정리하다보니 문제를 그래도 어찌저찌 풀긴 했다.

일단 문제 푸는 방식은 이대로 저 세가지 방식을 활용하고 다음부터는 시간제한을 좀 두는 방식도 도전해봐야겠다.