알고리즘문제 풀어보기/백준

백준-2515 전시장

rimugiri 2024. 10. 24. 05:37
728x90

해결과정 - DP, 투포인터

핵심은 두가지가 있다

1. 현재 그림을 보이게 할때 앞에 올수있는 가장 큰 그림 찾기 - 투포인터

2. 현재 그림보다 작은 그림들에대한 최대값 미리 구해두기 - DP

 

1.의 경우 n 시간안에 찾아야 하므로 완전탐색이 아닌 투포인터를 사용해주었다

2.의 경우 i번째그림을 걸려고할경우 1에서 구한 그림에대해 계산된 값을 이용해주고 i번째 그림을 걸지 않는경우 그전 그림에대해 계산해주면 된다

 

#include <bits/stdc++.h>

#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;


int main() {
    FAST;

    int n, s;
    cin >> n >> s;

    //first는 높이 second는 가격
    vector<pair<int, int>> pictures(n);
    //dp[0][i] 는 i번째를 고른경우 dp[1][i]는 i번째를 고르지 않은 경우
    vector<vector<int>> dp(2, vector<int>(n));
    //자신을 골랐을때 이전에 올수 있는 가장 큰 인덱스
    vector<int> prev(n);
    for (int i = 0; i < n; i++) {
		cin >> pictures[i].first;
        cin >> pictures[i].second;
	}

    sort(pictures.begin(), pictures.end());

    prev[0] = 0;

    int left = 0, right = 1;
    while(true){
        if (right == n) {
            break;
        }
        int diff = pictures[right].first - pictures[left].first;
        if (diff < s) {
            prev[right] = left - 1;
            right++;
		}
        else {
			left++;
		}
	}

    dp[0][0] = pictures[0].second;
    dp[1][0] = 0;

    for (int i = 1; i < n; i++) {
        int diff = pictures[i].first - pictures[i - 1].first;
        if (diff < s) {
            if (prev[i] == -1) {
                dp[0][i] = pictures[i].second;
            }
            else {
                dp[0][i] = max(dp[0][prev[i]], dp[1][prev[i]]) + pictures[i].second;
            }
            dp[1][i] = max(dp[0][i - 1], dp[1][i - 1]);
        }
        else {
            dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]) + pictures[i].second;
			dp[1][i] = max(dp[0][i - 1], dp[1][i - 1]);
        }
    }

    cout << max(dp[0][n - 1], dp[1][n - 1]) << "\n";
    return 0;
}

 

후기

항상 차근차근 문제를 보고 3분은 생각하고 풀자

728x90