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
'알고리즘문제 풀어보기 > 백준' 카테고리의 다른 글
백준 - 12738 가장 긴 증가하는 부분수열 (0) | 2024.10.27 |
---|---|
백준 - 2665 미로 만들기 (0) | 2024.10.24 |
백준 - 11444 피보나치 수열 6 (0) | 2024.10.24 |
백준 - 9252 LCS2 (0) | 2024.10.24 |
백준 - 2342 Dance Dance Revolution (0) | 2024.10.21 |