문제 링크입니다: https://www.acmicpc.net/problem/11057
슬슬 동적계획법에 대해 감을 잡아가는 것 같습니다!
#include <iostream>
#include <cstring> //memset
using namespace std;
const int MOD = 10007;
int N;
int cache[10][1001]; //시작하는 숫자(0~9), N<=1000
int uphill(void)
{
memset(cache, 0, sizeof(cache));
for (int i = 0; i < 10; i++) //초기값
cache[i][1] = 1; //0~9까지 하나씩
//j부터 9까지의 i-1 길이의 오름수들을 더하면
//j부터 시작하는 i 길이 오름수를 구할 수 있다
for (int i = 2; i <= N; i++)
for (int j = 0; j < 10; j++)
for (int k = j; k < 10; k++)
{
cache[j][i] += cache[k][i - 1];
cache[j][i] %= MOD; //여기서도 MOD로 나눈 나머지를 저장하는 것이 포인트
}
int sum = 0;
for (int i = 0; i < 10; i++)
sum += cache[i][N]; //0~9로부터 시작하는 오름수를 모두 더하고
return sum % MOD; //MOD로 나눈 나머지 출력
}
int main(void)
{
cin >> N;
if (N < 1 || N>1000)
exit(-1);
cout << uphill() << endl;
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 11048번 이동하기 (0) | 2018.02.22 |
---|---|
백준 2747번 피보나치 수, 2748번 피보나치 수 2 (0) | 2018.02.22 |
백준 2167번 2차원 배열의 합 (0) | 2018.02.19 |
백준 9465번 스티커 (0) | 2018.02.18 |
백준 2163번 초콜릿 자르기 (0) | 2018.02.16 |