[BOJ] #14501 퇴사

시간 제한	메모리 제한	정답 비율
2 초	512 MB	46.680%

 

14501번: 퇴사

 

주어진 N일 동안에 백준이가 최대의 이익을 볼 수 있도록 일을 선택해야 한다.

 

틀렸던 이유

시작하는 날짜를 st, 끝나는 날짜를 end 보수를 p 라고 봤을 때 end 값을 기준으로 오름차순 정렬을 하여 p를 더했다가 틀려버렸다.. 분명 2년 전 스터디하면서 풀었을 때는 누군가가 이렇게 풀었었는데 예외처리가 떠오르지 않아 dp로 고쳐서 다시 풀었다.

 

메모리	시간
1988 KB	0 ms

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
vector<pair<p, int>> v;
 
bool cmp(pair<p, int > a, pair<p, int> b) {
    return a.first.second < b.first.second;
}
int n;
int main() {
    scanf("%d", &n);
    for (int i = 1, a, b; i <= n; i++) {
        scanf("%d %d", &a, &b);
        v.push_back({ {i, i+a}, b });
    }
    sort(v.begin(), v.end(), cmp);
 
    int st = 0, end = 0, ans = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i].first.second > n+1) continue;
        if (v[i].first.first >= end) {
            ans += v[i].second;
            end = v[i].first.second;
        }
    }
    printf("%d", ans);
    return 0;
}
 

 

 

틀렸던 코드를 보고 싶다면 여기로...