백준 BOJ 10844 - 쉬운 계단 수

슬슬 바텀업 방식 DP의 감이 잡히는거같기도 하고...

그래도 역시 너무 섣부른거 같긴 하다 아직.

​

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

10844번: 쉬운 계단 수

그냥 dp배열을 1차원으로 만드려다

0으로 시작하는 수는 없다는 규칙때문에 배열을 2차원으로 짜냈다.

#include <stdio.h>

int dp[101][11] = {0};
int index(int k){ if(k==-1){return 10;} return k; }

int main(){
	int n,sum=0;
	scanf("%d", &n);
	for(int i=1; i<10; i++) dp[0][i] = 1;
	for(int i=0; i<n; i++){
		for(int j=0; j<10; j++){
			dp[i+1][index(j+1)] = ( dp[i+1][index(j+1)] + dp[i][j] ) % 1000000000;
			dp[i+1][index(j-1)] = ( dp[i+1][index(j-1)] + dp[i][j] ) % 1000000000;
		}
	}
	for(int i=0; i<10; i++) sum = (sum+dp[n-1][i])%1000000000;
	printf("%d", sum);
	return 0;
}

index 함수는 세그멘테이션 폴트가 일어나지 않도록 한다.

dp배열의 크기를 일부러 0부터 10까지 들어가도록 했는데,

그냥 찌꺼기값 담아놓는 인덱스를 10으로 정했다.

그래서 -1이라는 잘못된 인덱스가 들어오면 찌꺼기값에 대신 계산하도록 해주었다.

입력 받고 바로 포문을 한번 돌려줘서 초기값을 간단히 설정해주고,

이중 포문으로 dp를 작성해줬다.

​

숫자가 4일때, 3과 5가 계단 수이다.

이를 좀 더 일반화하자면, 숫자 j가 온다면, j+1과 j-1이 계단 수임을 말한다.

그래서 [i+1][index(j+1)]과 [i+1][index(j-1)],

즉 j의 계단수가 되는 두 배열 위치에 값을 더해주게 된다.

​

Dp[i][j]는 i = 계단수의 문자열 길이, j = 계단수의 첫번째 자리 숫자

일때의 경우의 수이고,

마지막으로 for문을 통해서 모든 첫번째 자리 숫자의 값을 더해주면

문자열의 길이가 주어질때의 계단수의 갯수를 구할 수 있게 된다.

​

​