[BOJ] 풀자 - Compy's Blog

풀자 #

유진이의 선생님은 유진이에게 몇 개의 문제를 풀라고 주었다. 유진이는 반드시 문제 1번을 먼저 풀어야 한다. 만약에 A번 문제를 풀었을 때, 유진이는 A+1번 문제를 풀거나, A+1번 문제를 건너뛰고 A+2번 문제를 푸는 것도 가능하다. 따라서, 1, 3, 4, 6과 같이 문제를 푸는 것은 가능하지만, 1, 3, 5, 8과 같이 문제를 푸는 것은 불가능하다.
유진이는 문제를 풀면서 흥미를 느낀다. 입력으로 주어지는 P배열은 유진이가 각 문제를 풀 때 느끼는 흥미도를 수치화 한 값이다.
유진이의 선생님은 유진이의 흥미도가 특정 범위내에 들면 문제를 푸는 것을 중지시키려고 한다. 만약 유진이가 지금까지 푼 문제의 흥미도의 최댓값과, 최솟값의 차이가 V보다 크거나 같으면 문제를 푸는 것을 중지하게 된다. 만약 이런 일이 절대 일어나지 않으면, 유진이는 문제를 다 풀게 된다. 유진이가 풀어야 하는 최소 문제수를 출력하는 프로그램을 작성하시오.

일단 간단한 조건이 있다. 문제를 딱 보는 순간 배열 P의 max값과 min값의 차이가 V보다 작으면 무조건 N을 출력하면 된다. 이 조건이 굉장히 중요하다.
나는 그냥 bruteforce 다 돌고나서 없으면 N을 반환하게 해놨더니 시간초가가 빻 ㅠㅜㅜ

이 조건을 처음에 넣고서, 그냥 재귀로 풀이하였따.

0번째는 무조건 풀어야 하기에 처음은 무조건 풀고서, 그 후에는 약간의 memo를 넣어서 시간을 아끼게 해줬어용

좀 예쁜코드는 아닌거 가타여

모드 즐거운 ps 하세용

정답 코드

#define MAX 2100000000
#define LIMIT 10'000'000
#include <iostream>
#include<vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
using ll = long long;

int n, v;
vector<int> problems;
int costs[1001];
int visited[1001][1001];
int result = MAX;

int limit = MAX;

void solution(int current, int interest_min, int interest_max, int count){
    if(current >= n || result <= count || current > limit) return;
    
    if(visited[current][count] > interest_max - interest_min) return;
    
    visited[current][count] = interest_max - interest_min;

    if(interest_max - interest_min >= v){
        result = min(count, result);
        limit = min(limit, current);
        return;
    }
    
    solution(current+1, min(interest_min, problems[current+1]), max(interest_max, problems[current+1]), count+1);
    if(current < n - 2) solution(current+2, min(interest_min, problems[current+2]), max(interest_max, problems[current+2]), count+1);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> v;
    
    
    problems.resize(n+1);
    
    int mymin = MAX, mymax = -1;
    for(int i = 0; i < n; i++){
        cin>> problems[i]; costs[i] = MAX;
        if(mymin > problems[i]) mymin = problems[i];
        if(mymax < problems[i]) mymax = problems[i];
        for(int j = 0; j < n; j++)
            visited[i][j] = -1;
    }
    
    if(mymax - mymin >= v) solution(0, problems[0], problems[0], 1);

    if(result == MAX) cout << n;
    else cout << result;
    
    
    return 0;
}

풀자#

풀자 #