[BOJ/백준] 11057 오르막 수

● [문제번호 11057] 오르막 수

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

11057번: 오르막 수

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

 

● 풀이 과정

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ dp[digit][last] : 자릿수(digit)이고 1의 자리수(last)로 만들어질 수 있는 총 경우의 수

 

2. 점화식 찾기

→ 이전 자릿수보다 큰 다음 자릿수 경우의 수에 이전 자릿수 경우의 수를 추가한다.

예제 입력3 풀이과정

 

 

3. 초기값 정하기

→ 1자리의 오르막 수는 각각 1가지씩이므로 모두 1이다.

 

 

● 주의 할 것

: 나머지 연산 주의한다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// dp[digit][last] : 자릿수(digit)이고 1의 자리수(last)로 만들어질 수 있는 총 경우의 수
int dp[1001][10];
int N;

void num()
{
    // 초기값 설정
    for(int last = 0; last < 10; last++)
        dp[1][last] = 1;
    
    // 점화식
    // 자릿수를 늘려가며
    for(int digit = 2; digit <= N; digit++)
        // 이전 자릿수의 경우의 수를
        for(int last = 0; last < 10; last++)
            // 다음 자릿수 중 큰 수에만 경우의 수 추가
            for(int index = last; index < 10; index++)
                dp[digit][index] = (dp[digit][index] + dp[digit - 1][last]) % 10007;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    num();
    
    // N 자리 자릿수의 경우의 수 총 합
    int total = 0;
    for(int last = 0; last < 10; last++)
        total = (total + dp[N][last]) % 10007;
    
    cout << total;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [401 - 다이나믹 프로그래밍 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	15988	1, 2, 3 더하기 3	https://pirateturtle.tistory.com/214
2	1149	RGB거리	https://pirateturtle.tistory.com/215
3	1309	동물원	https://pirateturtle.tistory.com/216
4	11057	오르막 수	https://pirateturtle.tistory.com/217
5	9465	스티커	https://pirateturtle.tistory.com/218
6	2156	포도주 시식	https://pirateturtle.tistory.com/219
7	1932	정수 삼각형	https://pirateturtle.tistory.com/220
8	11055	가장 큰 증가 부분 수열	https://pirateturtle.tistory.com/221
9	11722	가장 긴 감소하는 부분 수열	https://pirateturtle.tistory.com/222
10	11054	가장 긴 바이토닉 부분 수열	https://pirateturtle.tistory.com/223
11	13398	연속합 2	https://pirateturtle.tistory.com/224
12	2133	타일 채우기	https://pirateturtle.tistory.com/225