BOJ18244 변형 계단 수(C++)

---

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

태그 : dp

---

사고 과정

일단 보자마자 매 자릿수가 전 자릿수의 영향을 받기에 DP라는 생각이 들었다.

dp[i][j][k][l] = i번째자리가 j로 시작하며 k개 연속, l방향으로 증감한 수의 갯수로 설정하고 풀었다.

1개 증가하는 경우 = 직전까지 1개 연속 감소/2개 연속 감소한 1 작은 수 / 최초에 증/감하지 않은 1 작은 수

2개 증가하는 경우 = 직전까지 1개 증가한 1 작은 수

감소하는경우는 이 반대로 놓고, MOD 처리만 잘 해주면 된다.

---

코드

#include <iostream>
using namespace std;

#define MOD 1000000007

int n;
//dp[i][j][k][l] = i번째자리가 j로 시작하며 k개 연속으로 증감한 수. l이 증감 방향
//1 증가 0 감소
long long dp[100][10][3][2];
long long  ans;

void solve() {
	for (int i = 0; i < 10; ++i) {
		dp[0][i][0][0] = 1;
	}

	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < 10; ++j) {
			if (j - 1 >= 0) {
				//1개 증가
				dp[i][j][1][1] += dp[i - 1][j - 1][0][0];
				dp[i][j][1][1] %= MOD;

				dp[i][j][1][1] += dp[i - 1][j - 1][1][0];
				dp[i][j][1][1] %= MOD;

				dp[i][j][1][1] += dp[i - 1][j - 1][2][0];
				dp[i][j][1][1] %= MOD;

				//2개 증가
				dp[i][j][2][1] += dp[i - 1][j - 1][1][1];
				dp[i][j][2][1] %= MOD;
			}
			if (j + 1 < 10) {
				//1개 감소
				dp[i][j][1][0] += dp[i - 1][j + 1][0][0];
				dp[i][j][1][0] %= MOD;

				dp[i][j][1][0] += dp[i - 1][j + 1][1][1];
				dp[i][j][1][0] %= MOD;

				dp[i][j][1][0] += dp[i - 1][j + 1][2][1];
				dp[i][j][1][0] %= MOD;


				//2개 감소
				dp[i][j][2][0] += dp[i - 1][j + 1][1][0];
				dp[i][j][2][0] %= MOD;

			}
		}
	}
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 2; ++j) {
			ans += dp[n - 1][i][0][j];
			ans += dp[n - 1][i][1][j];
			ans += dp[n - 1][i][2][j];
			ans %= MOD;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	solve();

	cout << ans;
}

---

후기

골드3 dp치고는 비교적 쉬운 편이였던 것 같다.