[BOJ] 18858 : 훈련소로 가는 날

문제 링크

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

18858번: 훈련소로 가는 날

논산(Non-산)인 수열이 몇 개인지 출력하는 문제.

풀이

논산이란 Non-산 즉 산이 아닌 수열을 의미한다. a1 < a2 > a3 처럼 올라갔다 내려가는 형태의 수열을 산이라고 부르기로 한다.

여기서 DP배열을 어떻게 선언할지가 관건인데, 수열의 i번째 수에 대해서 3가지의 경우로 나누어서 생각할 수 있다.

1. i-1번째 수와 비교했을 때 i번째 수가 더 큰 경우. 즉, 올라온 경우(오르막)

2. i-1번째 수와 비교했을 때 i번째 수가 더 작은 경우. 즉, 내려온 경우(내리막)

3. i-1번째 수와 i번째 수가 같은 경우. 즉, 그대로(평지)

DP배열을 DP[1~M][수열의 몇번째 숫자인지(1~N)][오르막인지, 내리막인지 평지인지]

나는 오르막을 0, 평지를 1, 내리막을 2로 정했다.

1.  i-1번째 수 < i번째 수인 경우에는 즉 i-1 -> i 가 오르막인 경우에는 i-2 -> i-1 이 오르막이든 평지이든 내리막이든 상관없다. 오르막 -> 오르막, 평지 -> 오르막, 내리막 -> 오르막 모두 가능하기 때문이다.

2. i-1번째 수 = i번째 수 인 경우. 즉, i-1 -> i 가 평지인 경우에도 역시 i-2 -> i-1 은 오르막, 평지, 내리막 모두 상관없다.

오르막 -> 평지, 평지 -> 평지, 내리막 -> 평지 모두 가능하기 때문이다.

3. i-1번째 수 > i번째 수 인 경우. 즉, i-1 -> i가 내리막인 경우. 이때는 불가능한 상황이 발생한다. 만약 i-2 -> i-1이 오르막이었다면 i-2 -> i-1 -> i 는 오르막 -> 내리막으로 산이 형성된다. 그렇기 때문에 i-2 -> i-1 이 평지, 또는 내리막인 경우만 유효한 것으로 판단한다.

for (int i = 2; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			for (int k = 1; k < j; k++) {
				DP[j][i][0] += (DP[k][i - 1][0] + DP[k][i - 1][1] + DP[k][i - 1][2]);
				DP[j][i][0] %= mod;
			}
			DP[j][i][1] += (DP[j][i - 1][0] + DP[j][i - 1][1] + DP[j][i - 1][2]);
			DP[j][i][1] %= mod;
			for (int k = M; k > j; k--) {
				DP[j][i][2] += (DP[k][i - 1][1] + DP[k][i - 1][2]);
				DP[j][i][2] %= mod;
			}
		}
	}

그렇게 코드를 작서해보면 점화식은 이렇게 된다.

그리고 N이 만약 1또는 2라면 산이 형성될 수가 없기 때문에

if (N == 1) {
	cout << M << "\n";
	return 0;
}
else if (N <= 2) {
	cout << M * M << "\n";
	return 0;
}

초기에 예외를 걸어주었다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 1000 + 5;
int N, M;
ll DP[105][MAX_N][3];
 
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    if (N == 1) {
        cout << M << "\n";
        return 0;
    }
    else if (N <= 2) {
        cout << M * M << "\n";
        return 0;
    }
    for (int i = 1; i <= M; i++) {
        DP[i][2][0] = i - 1;
        DP[i][2][1] = 1;
        DP[i][2][2] = M - i;
    }
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            for (int k = 1; k < j; k++) {
                DP[j][i][0] += (DP[k][i - 1][0] + DP[k][i - 1][1] + DP[k][i - 1][2]);
                DP[j][i][0] %= mod;
            }
            DP[j][i][1] += (DP[j][i - 1][0] + DP[j][i - 1][1] + DP[j][i - 1][2]);
            DP[j][i][1] %= mod;
            for (int k = M; k > j; k--) {
                DP[j][i][2] += (DP[k][i - 1][1] + DP[k][i - 1][2]);
                DP[j][i][2] %= mod;
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= M; i++) {
        ans += (DP[i][N][0] + DP[i][N][1] + DP[i][N][2]);
        ans %= mod;
    }
    cout << ans << "\n";
    return 0;
}