백준 - 14501번 퇴사

문제

퇴사하기 전에 일정을 잘 짜서 돈을 최대한 벌고 싶을 때
어떻게 일정을 잡아야 좋을까?

생각

O(n^2)

1번째 날 전까지 최대로 벌 수 있는 돈,
2번째 날 전까지 ... 3번째 날 전까지 ... 이런 식으로
index날 전 까지 벌 수 있는 최대값을 저장해놓고
다른 날을 구할 때 사용하려고 함

for (int i = 0; i < n; i++) { //1번째 날, 2번째 날 ,,,
    // 퇴사 이후엔 일 못해
    if (t[i] + i > n) continue;

    for (int j = i - 1; j >= 0; j--) { //i날 전까지 일 한 날들 중
        if (t[j]+j <= i) { //j날에 일하고 i날 전에 끝날 수 있으면
            //j날 일 하고 온 상태가 최대겠네
            s[i] = max(s[i], p[j] + s[j]);
        }
    }

	//i날에 일 하고 번 돈이 최대 금액
    maxP = max(maxP, s[i] + p[i]);
}

근데 이렇게 하면 for문 2번 돌기 때문에 O(n^2)의 시간복잡도임

이 문제 바로 전에 풀었던 문제가
for문 2번 돌면서 가능한 경우 다 보는 문제기도 했고,
for문 한 번만에 푸는 법이 잘 안 떠올라서
검색해보니 for문 한 번에도 쉽게 가능하다.. ㅜ

O(n)

1번째 날 일 했을 때 안 했을 때 버는 돈,
2번째 날 ... 3번째 날... 이런식으로
어느 날으로 부터 일을 해서 최대로 받은 돈 혹은
일을 안 하고 최대로 받은 돈을 저장해가며
최대로 번 돈을 파악

for (int i = 0; i < n; i++) { //1번째 날, 2번째 날 ,,,
    if (t[i] + i <= n) { //일 할 수 있으면
        //일 한 경우 저장
        s[i + t[i]] = max(s[i + t[i]], s[i] + p[i]);
        maxP = max(maxP, s[i + t[i]]);
    }
	
    //일 안 하고 그냥 다음 날 된 경우 저장
    s[i + 1] = max(s[i + 1], s[i]);
    maxP = max(maxP, s[i + 1]);
}

for문 한 번으로 해결~~~

코드

O(n^2)

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

int n, maxP;
int t[20], p[20], s[20]; //index일 전까지 최대 얻을 수 있는 이익

int findMaxP() {
	for (int i = 0; i < n; i++) {
		if (t[i] + i > n) continue;

		for (int j = i - 1; j >= 0; j--) {
			if (t[j]+j <= i) {
				s[i] = max(s[i], p[j] + s[j]);
			}
		}
		
		maxP = max(maxP, s[i] + p[i]);
	}

	return maxP;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> t[i];
		cin >> p[i];
	}

	cout << findMaxP();

	return 0;
}

O(n)

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

int n, maxP;
int t[20], p[20], s[20]; //index일 까지 최대 얻을 수 있는 이익

int findMaxP() {
	for (int i = 0; i < n; i++) {
		if (t[i] + i <= n) {
			s[i + t[i]] = max(s[i + t[i]], s[i] + p[i]);
			maxP = max(maxP, s[i + t[i]]);
		}
		
		s[i + 1] = max(s[i + 1], s[i]);
		maxP = max(maxP, s[i + 1]);
	}

	return maxP;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> t[i];
		cin >> p[i];
	}

	cout << findMaxP();

	return 0;
}