[C++] 백준 11057번 오르막 수

다이나믹 프로그래밍 문제.

지난번에 풀었던 쉬운 계단 수 문제와 비슷한 문제였다.

[C++] 백준 10844번 쉬운 계단 수

지난 번에 이 문제를 풀었을 땐 풀기 어려워서 못 풀었었는데

비슷한 이문제는 비교적 쉽게 풀어서 이 때 정리를 나름 잘 한것 같아서 뿌듯했다.

 

문제 접근 방식

처음에 문제를 보자마자 위에서 설명했듯 쉬운 계단수를 풀었던 기억이 떠올렸다.

다이나믹 프로그래밍이라고 바로 생각했고 마지막 수에 따라

자리수의 마지막 수 이전에 어떤 수가 올 수 있는지 생각해서 풀었다.

※여기서 말하는 마지막 수는 1234567 처럼 마지막에 있는 수를 말하는 것이다.

즉, 원래는 첫째 자리수 이긴 하지만, 설명에 용이하게 마지막 자리수라고 설명하겠다.

 

• N번째에 마지막 자리수가 0인 수는, N - 1번째에서 마지막 자리수가 0인 수 밖에 올수 없다. 
• N번째에 마지막 자리수가 1인 수는, N - 1번째에서 마지막 자리수가 0, 1인 수가 올 수 있다.
• N번째에 마지막 자리수가 2인 수는, N - 1번째에서 마지막 자리수가 0, 1, 2인 수가 올 수 있다.
• ...
• N번째에 마지막 자리수가 9인 수는, N - 1번째에서 마지막 자리수가 0~9인 수가 올 수 있다.

이런 규칙을 얻을 수가 있다. 따라서 바로 코드로 구현해주면 된다.

 

사용한 STL과 변수

각 자리수를 담을 배열 dp 배열을 만들었다.

그리고 항상 그렇듯, 크기가 클 수 있는 (문제에서는 나머지 연산을 하라고 나와있으므로 이미 큰 수라고 알려준 것이다.)

수는 long long 자료형을 사용한다.

그리고 결과값은 dp[n][0]~ dp[n][9]를 모두 더한 값이므로 이를 담을 결과값 변수 result를 만들어준다.

 

메인함수

n을 입력받은 후,

n이 1인 경우 모든 수가 1이므로 1로 초기화 해준다.

그리고 3중 포문을 사용하게 된다. 이를 이용해서 값들을 구해준다.

dp[i][0] ~ dp[i][9]를 구하고 싶을때, (1 < i <= n)

• 가장 바깥쪽 for문은 자리수 2 ~ n까지의 범위를 나타내는 i이다.
• 가운데 for문은 마지막 수가 무엇인지 나타내는, 0~ 9까지의 내가 구하고 싶은 마지막 자리수를 나타낸다.
• 마지막 for문은 k는 0부터 j까지가 범위이다. 이전 자리 마지막 수 0 ~ j까지 더해줄 수 있는 것을 나타낸다.

이렇게 초기화를 해주고 마지막 for문을 돌려서 result 결과값에 더해주고 출력한다.

 

비슷한 문제에서 해맸던 경험이 도움이 많이 됐다.

모르는 문제를 찾아보고 정리하는 것은 도움이 정말 많이 되는 것 같다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.