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

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

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

 

이 문제는 dynamic programming 기법을 사용해 해결할 수 있다.

 

문제에서 주어지는 징검다리는 1번돌 부터 N번째 돌까지 건너갈 수 있는 여부를 확인한다.

그 다음 건너갈 수 있다면 dp 배열에 true를 넣는다. 

i번째 dp 배열의 요소가 false인 경우에는 건너갈 수 없는 경우이기 때문에 무시하고, true인 경우에만 건너갈 수 있는지 여부를 확인한다.

 

arr 배열 

1

4

1

3

1

 

1. dp 초기화

false

false

false

false

false

 

2. 1번째 돌의 경우 건널 수 있으니 true로 변경

true

false

false

false

false

 

3. 1번째 돌에서 건널 수 있는 돌 표시

true

false

true

false

false

 

4. 2번째 돌에서는 건널 수 없으니 무시

 

5. 3번째 돌에서 건널 수 있는 돌 표시

true

false

true

true

true

 

6. 마지막 돌 까지 건널 수 있으므로 "YES" 출력

 

#include<iostream>
#include<cstring>
using namespace std;

int N, K;
int arr[5001];
bool dp[5001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
    cin>> N >> K;
    for(int i = 1;i<=N;i++)
        cin>>arr[i];
    
    dp[1] = true;

    for(int i = 1; i<=N;i++){
        if(!dp[i]) continue;
        for(int j = i+1;j<=N;j++){
            long long now = (j-i) * (1 + abs(arr[i] - arr[j]));
            if(now <= K)
                dp[j] = true;
        }
        if(dp[N]){
            cout<<"YES"<<'\n';
            exit(0);
        }
    }
    cout<<"NO"<<'\n';
    return 0;
}