[실1][C++] 백준 10844번 쉬운 계단 수 (dp)

10844번: 쉬운 계단 수 (acmicpc.net)

+ 6.26 다시 품(모름)

 

풀이법

dp [자리 수][마지막 자리 숫자] 로 dp배열을 생성

1자리부터 만들 수 있는 계단 수의 갯수를 구하고 뒤에 숫자를 하나씩 붙여서 자릿수를 늘려가며 계산.

 

ex) 3자리,5로 끝나는 수 = (2자리,4로 끝나는 수) + (2자리,6으로 끝나는 수) 

      // 3자리,5로 끝나는 수는 2자리,4로 끝나는 수 뒤에 5라는 숫자만 붙이면 되니까. 

 

내 코드

#include<iostream>
#include <cmath>

# define FLOWDEFENDER 1000000000 //큰 숫자 overflow 방지

using namespace std;

int dp[101][10];

int main() {
	long answer = 0;
	int num;
	cin >> num;

	// dp[] 첫 단계 초기화
	dp[1][0] = 0;

	for (int i = 1; i <= 9; i++) {
		dp[1][i] = 1;
	}

	//dp 배열 계산
	for (int i = 2; i <= num; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0)
				dp[i][j] = dp[i - 1][j + 1];
			else if (j == 9)
				dp[i][j] = dp[i - 1][j - 1];
			else
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
			dp[i][j] %= FLOWDEFENDER;
		}
	}

	//n자릿수에서 가능한 모든 경우를 더하기
	for (int j = 0; j <= 9; j++) {
		answer += dp[num][j];
	}

	cout << answer % FLOWDEFENDER;

	return 0;
}

 

 

+ DP를 사용하여 쓰는 아이디어를 이끌어내는게 참 어렵다! 많이 풀어보면서 노하우들을 몸에 베게 해야겠다.

다 풀고도 답이 overflow되면서 에러가 나는걸 캐치하지 못함. FLOWDEFENDER로 값을 계속 줄여주도록 수정했더니 맞았다.

답이 큰 수라면 overflow를 늘 조심하자