[22869] 징검다리 건너기 (small)

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

22869번: 징검다리 건너기 (small)

<문제>

O(N^2)으로 풀이가 가능하므로 조건만 잘 구현해주면 간단히 해결할 수 있는 문제이다.

필요한것은 이동이 가능한지에 대한 true혹은 false의 값일 뿐이므로

dp[]를 bool형으로 선언해주고, 초기상태를 dp[1] = true; 로 표현해주었다.

 

이후로는 시작점을 의미하는 큰 for()와 도착점을 의미하는 작은 for()를 돌려서

i에서 j로 갈때의 cost가 K보다 작고 -> (j - i) * (1 + (abs(a[i] - a[j])))

i에 도달할 수 있을때 -> dp[i] == true

dp[j]를 true로 갱신해주면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int n, k, a[5001];
bool dp[5001];
int main(void) {
    int i, j;
    cin >> n >> k;
    for (i = 1; i <= n; i++) cin >> a[i];
    dp[1] = true;
    for (i = 1; i <= n - 1; i++) {
        for (j = i + 1; j <= n; j++) {
            int cost = (j - i) * (1 + (abs(a[i] - a[j])));
            if (cost <= k && dp[i] == true) {
                dp[j] = true;
            }
        }
    }
    dp[n] == true ? cout << "YES" : cout << "NO";
    return 0;
}