[BOJ] 11057 - 오르막 수 (C++)
문제
코드
#include <iostream>
using namespace std;
int N;
int dp[1001][10];
int main(void){
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> N;
for (int i = 0; i < 10; i++) dp[1][i] = 1;
for (int i = 2; i <= N; i++){
for (int j = 0; j < 10; j++){
for (int k = j; k < 10; k++){
dp[i][k] += dp[i-1][j];
dp[i][k] %= 10007;
}
}
}
int sum = 0;
for (int i = 0; i < 10; i++) sum += dp[N][i];
cout << sum % 10007;
return 0;
}
접근
이 문제를 보고 나름 자연스럽게 dp로 풀어야겠다고 생각이 들었다. 이전 단계에서 오르막의 규칙이 지켜진다면 앞으로도 지켜질 것이기 때문에 이전 값을 이용할 수 있기 때문이다. 그래서 dp 배열을 사용하였다.
dp[i][10] : i 자리의 숫자 중 0~9로 끝날 수 있는 수의 개수
만약 마지막 자리가 0이라면 이때 고려해야 하는 값들은 dp[i-1][0~9]이고, 마지막 자리가 8이라면 고려해야 하는 값들은 dp[i-1][8~9]이다. 따라서 이를 위해서 3중 for문을 사용하였다. 또한 1자리 숫자들의 경우도 만족할 수 있게 먼저 값을 1로 처리해주었다.
Author And Source
이 문제에 관하여([BOJ] 11057 - 오르막 수 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@keybomb/BOJ-11057-오르막-수-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)