[백준(BOJ) 15749번] Snow Boots 풀이

t[i] : i번 타일에 도착할 수 있으면 true, 없으면 false.

부츠를 1번부터 순서대로 신어보면서 t[i]를 채워가면 된다.

 

for 1 <= j <= B:

    1 <= k <= d[j]를 만족하는 어떤 k에 대해, t[i-k]가 true이면서 i-k번 타일과 i번 타일에서 j번 부츠를 신을 수 있는 경우 t[i] = true.

#include <iostream>

using namespace std;

int main() {
    int N, B, f[251], s[251], d[251];
    cin >> N >> B;
    for (int i = 1; i <= N; i++) cin >> f[i];
    for (int j = 1; j <= B; j++) cin >> s[j] >> d[j];

    bool t[251] = {false, true,};  // t[1] = true;
    int j;
    for (j = 1; j <= B; j++) {
        for (int i = 1; i <= N; i++) {
            if (s[j] >= f[i]) {  // If he can wear boots j on tile i.
                bool able = false;
                for (int k = 1; k <= d[j] && i - k >= 1; k++) {
                    if (t[i - k] && s[j] >= f[i - k]) {  // If he can wear boots j on tile i-k.
                        able = true;
                        break;
                    }
                }
                t[i] |= able;
            }
        }
        if (t[N]) break;
    }

    cout << j - 1;

    return 0;
}