[백준] 11057 오르막 수 (DP)
2020. 2. 27. 17:17
https://www.acmicpc.net/problem/11057
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.
www.acmicpc.net
동적 계획법 문제였습니다.
규칙은 찾았지만 구현하기 까다로웠습니다.
처음 생각
각 자리수 마다 오르막 수는 이전 자리수들의 경우의 수들을 계속해서 합쳐나가는? 식으로 접근함.
위의 방법을 함수로 구현하려다가 까다로워져서 다른방법 생각..
다른 방법
반복문을 통해서 위의 sum을 구현해봄.
일단 1자리 수는 모두 1로 초기화 해줍니다.
2자리 부터 점화식을 사용해 해결합니다.
k 를 시작하는 수로 생각하면
k부터 만들수 있는 오르막 수 는 이전 자리 수(n-1)에서 k부터 시작해서 9까지 만들 수 있는 경우의 수를 모두 더해주면 됩니다.
코드를 보는게 이해하기 더 쉬울것 같습니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 9466 팀 프로젝트(DFS, Cycle) (0) | 2020.03.04 |
|---|---|
| [백준] 1699 제곱수의 합 (Dynamic programming) (0) | 2020.03.02 |
| [백준] 15686 치킨 배달 (Brute force) (0) | 2020.02.23 |
| [백준] 17779 게리 맨더링 2 (2) | 2020.02.22 |
| [백준] 16234 인구 이동 (0) | 2020.02.18 |