[백준/c++] 11057번: 오르막 수

 

 

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

11057번: 오르막 수

 

 

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

수는 0으로 시작 가능

수의 길이 n이 주어졌을 때, 오르막 수의 개수 구하기(10,007로 나눈 나머지 출력)

 

 

 

---

 

 

길이 1 -> 0, 1, 2, 3,..., 9 = 총 10개

길이 2 -> 00, 01, ... , 11, 12, 13,..., 99 = 총 55개

길이 n -> 몇 개일까?

 

길이 i일 때의 오르막 수의 개수를 구하다보면 다음 길이의 총 합도 구하기 쉽다(메모리 절약, 시간 절약)

dp [i][j] -> 길이(자릿수)가 i이고 j로 끝나는 오르막 수의 개수

 

테스트 예제를 하나 만들어서 직접 값을 적어내리다 보면 규칙이 보인다.

dp [3][4] -> 3 자릿수 && 4로 끝나는 수

004    114    224    334    444
014    124    234    344    
024    134    244
034    144
044

⬇️

004    014    024    034    044
       114    124    134    144
              224    234    244
                     334    344
                            444

위의 조건에 맞는 수를 쭉 나열하고, 우리가 찾아야 하는 자릿수+같은 숫자로 끝나는 수라는 조건이 있으므로 그것에 맞는 점화식을 만들어야 한다. 그러므로 4로 끝나는 수 앞의 수도 어떠한 수로 끝나는 수여야 한다. 정리를 하면 2번째와 같은 형태가 보인다.

 

00    01    02    03    04
      11    12    13    14
            22    23    24
                  33    34
                        44

dp [2][0] - dp [2][1] - dp [2][2] - dp [2][3] - dp [2][4]

이것들의 합이 바로 dp [3][4]의 오르막 수이다.

즉, dp [i][j] = dp [i-1][0] + dp [i-1][1] +... + dp [i-1][j]

 

#include <iostream>
#define num 1002
using namespace std;
int n, dp[num][10];

void solution(){
    for(int i=0; i<10; i++) dp[1][i] = 1; //초기값 -> i자릿수이고 1로 끝나는 수
    for(int len=2; len<=n; len++){
        //자리수 len 이고 last로 끝나는 수
        for(int last=0; last<10; last++){
            for(int prev=0; prev<=last; prev++){
                dp[len][last] += dp[len-1][prev];
                dp[len][last] %= 10007;
            }
        }
    }
    
    int ans = 0;
    for(int i=0; i<10; i++){
        ans += dp[n][i];
        ans %= 10007;
    }
    cout << ans << '\n';
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    solution();
    return 0;
}

 

 

규칙만 잘 찾으면 쉽게 풀리는 재미있는 문제..!😇

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!