BOJ 15749 Snow Boots

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

15749번: Snow Boots

 

간단한 DP문제였지만, 코드를 확인하지 못해 기록을 남긴다.

신발을 갈아신어야 하는 조건이 

for(int k=1; k<=boots[i-1].second && j+k < n; k++){ 
	if(road[j+k] <= boots[i-1].first ) check[i][j+k] = true;
}

에서 걸러질 수 있다고 생각했으나, 신발을 갈아신는 step 을 나아갈 때가 아니라, 이전 신발의 기록을 가지고 현재 신발을 신고 나아갈 수 있는지 확인하기 전에 확인해야했었다. 그래서 맞왜틀을 1시간동안 하고 있었다.

나의 코드는 아래와 같다.

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

int n,b;
vector<int> road;
vector<pair<int, int>> boots;
bool check[251][250];
int main(){

    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> n >> b;
    road.resize(n); boots.resize(b);
    for(int i=0;i<n;i++) cin >> road[i];
    for(int i=0;i<b;i++) cin >> boots[i].first >> boots[i].second;

    check[0][0] = 1;
    for(int i=1;i<=b;i++){
        for(int j=0;j<n;j++){
            if(check[i-1][j]) check[i][j] = true;
            if(!check[i][j]) continue;
            if(road[j] > boots[i-1].first) continue;
            for(int k=1; k<=boots[i-1].second && j+k < n; k++){ 
                if(road[j+k] <= boots[i-1].first ) check[i][j+k] = true;
            }
        } 
        if(check[i][n-1]) {
            cout << i-1 << "\n";
            return 0;
        }
    }
    return 0;
}