📌문제
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;
}
'[ 알고리즘 ] > DP' 카테고리의 다른 글
[프로그래머스] 도둑질 (0) | 2022.06.29 |
---|---|
[프로그래머스] 등굣길 (0) | 2022.06.29 |
[프로그래머스] 정수 삼각형 (0) | 2022.06.29 |
[프로그래머스] N으로 표현 (0) | 2022.06.29 |
[백준] 17968. Fire on Field (0) | 2022.06.29 |