백준 14501번 : 퇴사
링크 : https://www.acmicpc.net/problem/14501
찾다보니 15486번 문제는 조건만 바뀐 것이었다. 15486번 문제까지 해결하려 했다면 정말로 이 문제의 핵심 안에 해결하는 것이 중요했다.
15486번 문제 링크 : https://www.acmicpc.net/problem/15486
오.. 며칠만의 알고리즘. 쉬운거 선택해서 뚝딱하려고 했지만 부르트 포스.. 쉽지않네.. 시작해보자.
문제 읽기
N일동안 일할 예정. 에 적혀있는 일수만큼 상담이 걸리며 그에 따른 비용은 에 적혀있다. 마지막 일자 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문까지 이용해 으로 푸는 기이한 알고리즘을 생각해내었다.
이번 문제의 포인트는 역순으로 접근하는 것이였다. 선택을 앞에서부터 시작하든 뒤에서부터 시작하든 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
은 계속 최대값으로 갱신해준다.
이렇게도 접근할 수 있고 저렇게도 접근할 수 있다는 것을 잊지 말아야한다. 이번에 역순으로 접근하는 것을 배웠으므로 제발 기억해서 다음에 알고리즘을 풀 때 적용할 수 있어야 한다.
Author And Source
이 문제에 관하여(백준 14501번 : 퇴사), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ntbij29/백준-14501번-퇴사저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)