백준 14501번 : 퇴사

dldzm·2021년 2월 2일
0

알고리즘 공부

목록 보기
20/42
post-thumbnail

링크 : https://www.acmicpc.net/problem/14501

찾다보니 15486번 문제는 조건만 바뀐 것이었다. 15486번 문제까지 해결하려 했다면 정말로 이 문제의 핵심 O(N)O(N)안에 해결하는 것이 중요했다.

15486번 문제 링크 : https://www.acmicpc.net/problem/15486


오.. 며칠만의 알고리즘. 쉬운거 선택해서 뚝딱하려고 했지만 부르트 포스.. 쉽지않네.. 시작해보자.

문제 읽기

N일동안 일할 예정. TiT_i에 적혀있는 일수만큼 상담이 걸리며 그에 따른 비용은 PiP_i에 적혀있다. 마지막 일자 N일을 넘어가면서 상담할 수는 없다. 이를 통해 최대 수익을 얻자.

참고 링크 : https://sihyungyou.github.io/baekjoon-14501/

코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int N, ans = 0;
	int ti[17]{ 0, }, pi[17]{ 0, };
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> ti[i] >> pi[i];

	for (int i = N; i >= 1; i--) {
		if ((i + ti[i]) > N+1)
			pi[i] = pi[i + 1]; 
		else {
		   	pi[i] = max(pi[i+1], pi[i] + pi[i + ti[i]]); 
		   	ans = max(ans, pi[i]);
		}
	}
	cout << ans << endl;
	return 0;
}

분석

처음에는 앞에서부터 시작해서 이중 for문을 사용하여 while문까지 이용해 O(N3)O(N^3)으로 푸는 기이한 알고리즘을 생각해내었다.

이번 문제의 포인트는 역순으로 접근하는 것이였다. 선택을 앞에서부터 시작하든 뒤에서부터 시작하든 N일 안에만 끝내면 되었기 때문이다.

문제를 쉽게 접근하기 위해 보통 0으로 시작하는 것에서 벗어나 1로 시작하는 것도 고려해야 한다.

for (int i = N; i >= 1; i--)

마지막 날부터 고려하자. 퇴사는 N+1일에 하므로 모든 일은 N일만에 끝나야 한다.

if ((i + ti[i]) > N+1)
	pi[i] = pi[i + 1]; 

만약 접근하는 i일에 ti[i]일만큼의 상담일을 더하게 되면 N+1안에 끝낼 수 있을 것인가 확인한다. 만약 N+1일보다 더 걸리면 i일에 걸려있는 상담은 선택할 수 없으므로 ti[i+1]까지 계산한 값을 가져온다. 다시 강조하자면 지금 우리는 역순으로 진행중이다. 앞에서부터 시작했다면 ti[i-1]까지 계산한 값을 가져오는 것이다.

else {
	pi[i] = max(pi[i+1], pi[i] + pi[i + ti[i]]); 
    	ans = max(ans, pi[i]);
}

i일의 상담을 선택할 수 있는 상황이다. 그렇다면 pi[i] + pi[i + ti[i]] 즉 해당 i일의 상담 비용 pi[i]에 선택한다면 이후 ti[i]일만큼은 일을 하지 못하므로 계산해놓은 비용을 가져온다. 그리고 pi[i+1]i일의 상담을 선택할 수 있었음에도 불구하고 선택하지 않았을 때의 비용까지 가져와 최대값을 계산하여 pi[i]에 넣어준다.

ans은 계속 최대값으로 갱신해준다.


이렇게도 접근할 수 있고 저렇게도 접근할 수 있다는 것을 잊지 말아야한다. 이번에 역순으로 접근하는 것을 배웠으므로 제발 기억해서 다음에 알고리즘을 풀 때 적용할 수 있어야 한다.

profile
🛰️ 2021 fall ~

0개의 댓글