[백준/C++]#10844 - 쉬운 계단 수

풀이

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int a[101][101];	// 2차원 배열 정의
	for (int i=1; i<=9; i++) a[1][i]=1;	// n=1일 때 값 저장
	for (int i=2; i<=n; i++) {		// 2~n번까지 반복
		for (int j=0; j<=9; j++) {
			a[i][j]=0;		// 초기값 0 대입
			if (j >= 1) a[i][j]+=a[i-1][j-1];
			if (j <= 8) a[i][j]+=a[i-1][j+1];
            a[i][j] %= 1000000000;
		}
	}
	long long ans=0;
	for (int i=0; i<=9; i++) ans+=a[n][i];	// n일 때의 모든 값 합함
    ans %= 1000000000;
	cout << ans;
	return 0;
}

개념

어렵게 풀었지만 이름은 쉬운 계단수인 다이나믹 프로그래밍 문제이다. 

문제의 조건에서 나와있는 1,000,000,000 으로 나눈 나머지를 출력하라는 것을 보면 자료형 long long을 사용해야함을 알 수 있다.

---

풀이 

쉬운 계단수를 구하기 위해 상황을 간단히 나눠야한다.

맨 뒤 자릿수의 값(L)에 따라 다음 연산(D[N])이 달라지므로, 이차원 배열을 사용한다.

①a[N][L]=a[N-1][L-1] + a[N-1][L+1]

     (L : 1~8)

②a[N][1]=a[N-1][0]

③a[N][9]=a[N-1][8]

 

이제 이중 반복문을 사용하고, 각 상황을 if로 나눠서 계산한다.

---

+a

다이나믹 프로그래밍 문제에 도저히 익숙해지지 않는다.

이전까지 느낀 바는 복잡한 과정을 단순한 알고리즘을 통해서 간단한 결과로 출력하는 느낌이었다.

이번 문제는 좀 더 구체적인 설정을 통해 문제를 해결할 수 있었다.

확실한 상황으로 문제를 조각내는 것이 중요한 것 같다.