[C] 백준 - 10844번: 쉬운 계단 수

3월 17일(금) - 동적계획법 1 (10844번)

10844번: 쉬운 계단 수

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 지금까지 풀어본 동적계획법 문제중에서 dp를 어찌 설정해야할지 가장 많이 고민한 문제이다

- 처음에는 dp배열을 1차원으로 몇자리의 수인지만 인덱스값으로 표현했더니, 반복문에서 활용할 조건이 부족함

- 다음으로 dp배열을 2차원으로 바꾸고, [N개 자릿수][가장 처음 숫자]로 설정했더니 풀이과정에서 다시 꼬임

- 마지막으로 dp[N개 자릿수][가장 마지막 숫자 그 자체]로 설정했더니 풀이가 진행됨

 

- 위의 결정을 토대로 진행한다면, 일단 1개 자릿수인 경우에는 dp[1][1] ~ dp[1][9] 까지 모두 1을 넣는다

  물론 0으로 시작은 못하기때문에 dp[1][0] = 0

- 이후 2개 자릿수 부터는 가장 마지막 숫자가

  0인 경우 / 9인 경우 / 두 경우를 제외한 1~8인 경우 이렇게 3가지로 나누어서 각각 dp[i][j]값을 계산한다

- 마지막 숫자로 0이 나오려면, 직전 숫자가 1인 경우에만 가능하므로 dp[i][j] = dp[i-1][1]

- 마지막 숫자로 9가 나오려면, 직전 숫자가 8인 경우에만 가능하므로 dp[i][j] = dp[i-1][8]

 

나중에 처음부터 다시 한 번 풀어보아야할듯

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

수정 전
else
{
	dp[i][j] = dp[i - 1][j - 1] + 1;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
수정 후
else
{
	dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
}

1. j가 0 이나 9가 아닌 1~8사이인 경우에는 1~8보다 1이 작은 수, 1이 큰 수 이렇게 2가지가 존재하기 때문에

단순히 dp[i][j]에 1을 더하면 될 것 이라고 생각

잘못된 출력값이 나옴

-> 동적계획법을 적용하면서 i가 커지며 숫자의 길이가 커지는 경우를 고려했을때,

    단순히 +1 이 아닌 dp[i-1][j-1]을 더해주는 것으로 변경

 

2. 반복문안에 위치한 if - else if - else 구문마다 %1000000000 계산을 넣지 않고, 마지막 sum에서만 계산

-> 틀림

-> 왜 틀렸는지 고민하다가 설마?하며 모든 조건문의 안쪽에 %1000000000을 넣자 정답처리

-> 이유 모르겠음

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int MAX(int x, int y)
{
	return ((x > y) ? x : y);
}

int main(void)
{
	int dp[101][10];

	int N;
	scanf("%d", &N);
	for (int i = 1; i < 10; i++)
	{
		dp[1][i] = 1;
	}

	dp[1][0] = 0;
	for (int i = 2; i < N + 1; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (j == 0)
			{
				dp[i][j] = dp[i - 1][1] % 1000000000;
			}
			else if (j == 9)
			{
				dp[i][j] = dp[i - 1][8] % 1000000000;
			}
			else
			{
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
			}
		}
	}

	int sum = 0;
	for (int i = 0; i < 10; i++)
	{
		sum = (sum + dp[N][i]) % 1000000000;
	}

	printf("%d", sum);
	return 0;
}

/*
1 2 3 4 5 6 7 8 9
10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98
101 121 123 210 212 232 234 ...876 878 898 987 989
*/

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ