주다람
개미는 뚠뚠🎵 오늘도 뚠뚠🎵 열심히 개발하네✨
주다람
전체 방문자
오늘
어제
  • 분류 전체보기
    • 💭 기록해보자
      • BackEnd
      • FrontEnd
      • 회고
    • 💻 수업정리 (2020)
      • 오라클
      • 자바
      • CSS & HTML
      • JavaScript
      • Servlet
      • JSP
    • 📚 알고리즘
      • DP(다이나믹 프로그래밍)
      • 탐색(BFS,DFS)
      • 다익스트라
      • 순열과 조합
      • 백트래킹
      • 이분탐색(binarySearch)
      • 탐욕(Greedy)
      • 스택,큐,덱(Stack,Queue,Deque)
      • 유니온파인드(Union-Find)

블로그 메뉴

  • 홈

공지사항

인기 글

태그

  • group by
  • oracle
  • background-gradient
  • 날짜함수
  • 오라클
  • 박스모델
  • 문자함수
  • 숫자함수
  • 변환함수
  • 함수
  • 일반함수
  • 그룹함수

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
주다람

개미는 뚠뚠🎵 오늘도 뚠뚠🎵 열심히 개발하네✨

📚 알고리즘/DP(다이나믹 프로그래밍)

[백준 11057] 오르막수_dp(c++)

2020. 5. 31. 16:18

1.문제

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

 

11057번: 오르막 수

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수�

www.acmicpc.net

2.접근방법

  1. 이것도 처음에 dfs백트래킹인지 dp인지 헷갈렸음(결국 너무 생각해내기 어려워서 다른 사람들 아이디어 살짝 봤다..)
  2. 나의 바로 전에 숫자가 무엇이 오는지에 따라 고를 수 있는 수가 달라짐

 

3.문제풀이

dp[] (행의 인덱스) dp[][] (열의 인덱스
자리수를 표현 0~9까지의 숫자를 표현
  1. n까지의 자리수 중에서 첫번째 자리수는 모든 숫자가 다 배치될 수 있으므로 1로 초기화 시켜준다.
  2. 2번째 자리수 부터는 1번째 자리수에서 어떤 숫자가 뽑혔는지에 따라 경우의 수가 달라진다.
  3. 2번째 자리수부터 n자리수까지 for문 (첫번째 for문) 을 돌면서 0~9까지의 숫자를 선택하는데 (두번째 for문) 
  4. n-1번째 숫자를 j를 골랐다면 n번째 숫자는 j이거나 j이상의 숫자를 뽑아야 한다.(세번째 for문)
  5. 결국 n자리번째에 오는 0~9까지 인덱스에는 해당 숫자로 n번째자리를 차지할때의 경우의 수가 카운팅 되어있을 것이다.
  6. 출력할때 dp[n][0~9]를 += 해서 값을 출력하면 끝!
  7. 참고) 출력할때의 값도 10007로 나눠줘야 하고, dp의 각 합을 구할때에도 10007로 나눈 나머지로 저장해야한다..여기서 시간 잡아먹었다..

 

4.전체코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n;
 
int main() {
    cin >> n;
    int** dp = new int*[n + 1];
    memset(dp, 0, sizeof(n + 1));
 
    for (int i = 0; i < n + 1; i++) {
        dp[i] = new int[9];
        memset(dp[i], 0, sizeof(int) * 9);
    }
 
    for (int i = 0; i <= 9; i++) {
        dp[1][i] = 1;
    }
 
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = j; k <= 9; k++) {
                dp[i][j] += dp[i - 1][k];
                dp[i][j] %= 10007;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i <= 9; i++) {
        sum += dp[n][i];
    }
    cout << sum % 10007 << "\n";
    
    return 0;
}
Colored by Color Scripter
cs

'📚 알고리즘 > DP(다이나믹 프로그래밍)' 카테고리의 다른 글

[백준 11727] 2×n 타일링 2_dp(c++)  (0) 2020.06.14
[백준 2096] 내려가기_dp(c++)  (0) 2020.06.14
[백준 11048] 이동하기(c++)  (0) 2020.05.24
[백준 1495] 기타리스트(c++)  (0) 2020.05.24
[백준 17069] 파이프 옮기기 2(C++)  (0) 2020.05.22
    '📚 알고리즘/DP(다이나믹 프로그래밍)' 카테고리의 다른 글
    • [백준 11727] 2×n 타일링 2_dp(c++)
    • [백준 2096] 내려가기_dp(c++)
    • [백준 11048] 이동하기(c++)
    • [백준 1495] 기타리스트(c++)
    주다람
    주다람
    신입 어린이 -> 주니어개발자 성장중

    티스토리툴바