[백준] 17979. What's Mine is Mine

 

📌문제

https://www.acmicpc.net/problem/17979

 

🎖️난이도

 

✔️풀이

# sol1) pypy3으로 제출시 정답 (python3은 시간초과)

x = input()
m, n = map(int, x.split())
type_price = [0]*m
for i in range(m):
    type_price[i] = int(input())

task_list = [0]*n
for i in range(n):
    x = input()
    tmp_list = list(map(int, x.split(' '))) # [s, e, t]
    tmp_list[2] = (tmp_list[1] - tmp_list[0]) * type_price[tmp_list[2]-1]
    task_list[i] = tmp_list

task_list.sort(key = lambda x : x[0])
print('task_list :', task_list)


accum_max = [0]*n
final_max = 0
for i in range(n):
    tmp_s = task_list[i][0]
    tmp_max = 0
    j = i-1
    while j >= 0:
        if task_list[j][1] <= tmp_s :
            tmp_max = max(tmp_max, accum_max[j])
        j -= 1
    accum_max[i] = task_list[i][2] + tmp_max
    final_max = max(final_max, accum_max[i])

print('accum_max :', accum_max)
print(final_max)

 

// sol2) C++

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <math.h>
#include <tuple>

using namespace std;

int m, n;
int type_price[101]; // 각각 얼마짜리인지 m가지 값 받은거
int task_list[10001][3]; // 전체 2차원 배열 입력받은거
int accum_max[10001];


int main() {
    cin >> m >> n;

    for (int i = 0; i < m; i++) {
        scanf("%d", &(type_price[i]));
    }

    vector<tuple<int, int, int>> tupleVec;

    for (int i = 0; i < n; i++) 
    {
        scanf("%d %d %d", &(task_list[i][0]), &(task_list[i][1]), &(task_list[i][2]));
        task_list[i][2] = (task_list[i][1] - task_list[i][0])* type_price[task_list[i][2]-1];
        tuple <int, int, int> tmp;
        tmp = make_tuple(task_list[i][0], task_list[i][1], task_list[i][2]);
        cout << "this is make_tuple : " << get<0>(tmp) << ' ' << get<1>(tmp) << ' ' << get<2>(tmp) << ' ' << endl;
        tupleVec.push_back(tmp);
    }

    //일단 s로 정렬 해주기 ==> <tuple>, tie, lambda 이용 (3개 이상의 key로 정렬)

    cout << "before sort" << endl; // 정렬 전

    for (int i = 0; i < n; i++)
    {
        cout << get<0>(tupleVec[i]) << ' ' << get<1>(tupleVec[i]) << ' ' << get<2>(tupleVec[i]) << ' ' << endl;
    }


    sort(begin(tupleVec), end(tupleVec), [](tuple<int, int, int> a, tuple<int, int, int> b) {
        return (tie(get<0>(a), get<1>(a), get<2>(a)) < tie(get<0>(b), get<1>(b), get<2>(b)));
    });


    cout << "after sort" << endl; // 정렬 후

    for (int i = 0; i < n; i++)
    {
        cout << get<0>(tupleVec[i]) << ' ' << get<1>(tupleVec[i]) << ' ' << get<2>(tupleVec[i]) << ' ' << endl;
    }


    // 누적 max들 구해가며 최종 max까지 한번에 구하기
    int final_max = 0;
    for (int i = 0; i < n; i++) {
        int tmp_s = get<0>(tupleVec[i]);
        int tmp_max = 0;
        for (int j = i-1; j >= 0; j--) {  // tmp_s 이전까지에 다 포함
            if (get<1>(tupleVec[j]) <= tmp_s) {
                tmp_max = max(tmp_max, accum_max[j]);
            }
            continue;
        }
        accum_max[i] = get<2>(tupleVec[i]) + tmp_max;
        final_max = max(final_max, accum_max[i]);
    }


    /* 각 단계에서의 누적 최댓값들 출력
    for (int i = 0; i < n; i++)
    {
        cout << accum_max[i] << endl;
    }
    */

    cout << final_max << endl;

    return 0;
}