Be myself :: [baekjoon 11057]오르막 수

달력

32024  이전 다음

  • 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

간단한 dp문제이다. 길이가 N일떄 마지막 숫자를 하나의 상태로 두고 이차원 배열로 만들어서 상태dp로 풀어준다. 그래서 결과 값은 dp[N][i] (i는 0~9까지)값을 모두 더한 값이 되겠다.

코드도 단순하다.


#include <stdio.h>
#include <iostream>
using namespace std;

int dp[1001][10];
int main()
{
	int N;
	int ans = 0;
	scanf("%d", &N);
	dp[1][0] = 1;
	for (int i = 1; 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 >= 0; k--)
			{
				dp[i][j] +=  (dp[i-1][k]) % 10007;
			}
		}
	}
	
	for (int i = 0; i <= 9; i++)
	{
		ans += (dp[N][i]) % 10007;
	}
	printf("%d\n", ans % 10007);
	return 0;
}

'Algorithm' 카테고리의 다른 글

[sw expert]모의sw역량테스트 보호필름  (1) 2017.10.09
[baekjoon 1500]최대 곱  (0) 2017.09.28
[baekjoon 11727] 2*n타일링2  (0) 2017.08.11
[algospot]Synchronizing Clocks  (0) 2016.01.28
[Algospot]PICNIC  (0) 2016.01.07
Posted by flack3r
|