< BOJ > 11057 - 오르막 수

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

11057번: 오르막 수

11057번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 오르막 수 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 14886 7187 5658 47.682% 문제 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0...

www.acmicpc.net

문제 조건

​

문제

---

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

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

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

​

​

입력

---

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

​

​

출력

---

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

​

​

예제 입력 1

---

1

예제 출력 1

---

10

예제 입력 2

---

2

예제 출력 2

---

55

예제 입력 3

---

3

예제 출력 3

220

​

​

​

해결 방법

DP를 이용해서 풀면 되는 간단한 문제이다.

N까지의 숫자에서 마지막 숫자를 정해주고 그 마지막 숫자에 해당하는 것에 포함되는 오르막 수를 구한뒤

모두 더해주면 된다.

​

d[N][L] += d[N-1][0~L]

​

​

소스코드

#include<cstdio>
#include<iostream>
#define mod 10007

using namespace std;

int n;

int d[1001][10]; //n개의 길이까지의 오르막 수
int res =0;


void bottom_up(){
    for(int i=0;i<=9;i++){
        d[1][i] = 1;
    }
    for(int i=2;i<=n;i++){
        for(int j=0;j<=9;j++){
            for(int k=0;k<=j;k++){
                d[i][j] += d[i-1][k];
                d[i][j] %= mod;
            }
        }
    }
    for(int i=0;i<=9;i++) res += d[n][i];
}

int main(){
    cin >> n;
    bottom_up();
    printf("%d",res%mod);
    return 0;
}

배운점

1. 다이나믹 프로그래밍이라고 해서 항상 위에서부터 쪼개나가는 Top Down 방식에 대해서만 고집했던 것 같다.

아래서 부터 올라가는 Bottom Up 방식에 대해서도 접근하는 방법을 조금 익혀둬야 할 것 같다.

​

2. res를 10007로 나누라는 문제 조건이 있었는데 그걸 생각하지 못하고 제출하였을 때 틀렸다는 답이 출력되었다.

이것을 해결하기 위해 mod를 define해서 함으로써 조금 간단하게 해서 까먹는 일을 줄일 수 있었다.

​

Github

https://github.com/ryudonghun78/Problem_Solving/blob/master/Baekjoon_Algorithm/DP/11057.cpp