(백준 10844번 쉬운 계단의 수 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 8

출근 전 한문제 컷! 이라고 말하기엔 그제부터 풀었던 쉬운 계단의 수 문제 ㅎㅎ

백준 10844번

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

10844번: 쉬운 계단 수

 

풀이는 간단하다!(라고 말하고 생각하는데 하루 걸렸다)

 

f(n)을 n자리 계단수의 갯수라고 정의하면

f(n+1) = 2 * f(n) - {n자리 계단수 중 마지막 자리가 0또는 9인 수의 갯수}로 나타낼 수 있다.

마지막 자리가 0 또는 9인 수를 알기 위해 DP[n][10]을 만들어 기록해주기만 하면 완성!

 

마지막 자리수가 1인 수만이 그 다음 숫자의 마지막 수를 0으로 만들 수 있고,

마지막 자리수가 8인 수만이 그 다음 숫자의 마지막 수를 9로 만들 수 있다!!

 

이 문제는 오버플로우가 잘 나니(이것 때문에 또 시간을 좀 썼다...^^) 모든 long long은 mod 1000000000를 해서 풀기를 권한다!!

백준 10430번에서 get

#define  _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 101, M = 1000000000;
int N;
long long  DP[MAX_N][10], result = 0;


int main() {
	scanf("%d", &N);
	//for (int i = 0; i < N; i++) fill_n(DP[i], 10, -1);
	fill_n(DP[0], 10, 1); DP[0][0] = 0;
	if (N == 1) { printf("9"); return 0; }
	for (int i = 1; i < N; i++) {
		DP[i][0] = DP[i - 1][1]%M;
		for (int j = 1; j < 9; j++) {
			DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % M;
		}
		DP[i][9] = (DP[i - 1][8]) % M;
	}
	for (int i = 0; i <= 9; i++) result += DP[N - 1][i]%1000000000;

	
	printf("%lld", result % M);
	return 0;
}

 

🌟나머지에 대해 익히기 좋은 연습문제(10430번)도 추천 🌟

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

10430번: 나머지

 

헤헤^^