끄적끄적
백준 [14501] 퇴사 본문
출처 : https://www.acmicpc.net/problem/14501
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
#include<algorithm> | |
using namespace std; | |
int T[16];//걸리는 기간 | |
int P[16];//받을 수 있는 금액 | |
int dp[16]; | |
int cur_max = 0; | |
int main() { | |
ios::sync_with_stdio(false); | |
cin.tie(0); | |
cout.tie(0); | |
int N, t, p; | |
cin >> N; | |
for (int i = 1; i <= N; i++) { | |
cin >> t >> p; | |
T[i] = t; | |
P[i] = p; | |
} | |
//N+1일째 퇴사를 하므로 N일동안 상담 후 N+1에 돈받기 가능 | |
for (int i = 1; i <= N + 1; i++) { | |
cur_max = max(cur_max, dp[i]); | |
if (i + T[i] > N + 1) continue; | |
dp[i + T[i]] = max(dp[i + T[i]], cur_max + P[i]); | |
} | |
cout << cur_max << '\n'; | |
return 0; | |
} |
dp
이미 저장되어 있는 값과(현재 날짜에서 상담을 하지 않는 경우), 현재 날짜에서 상담을 하여 저장되는 값 중 큰 값을 저장해주면 된다.
cur_max 변수를 사용한 이유
-> 예를 들어 7일에 저장된 값이 60이고 그 값이 그대로 간다면 8일에 저장된 값도 60이어야 하는데, 초기값은 0이니까 대입해주는 작업 필요해서 cur_max 변수를 사용한 것
'코테준비 > 백준' 카테고리의 다른 글
백준 [14495] 피보나치 비스무리한 수열 (0) | 2022.08.30 |
---|---|
백준 [1965] 상자넣기 (0) | 2022.08.26 |
백준 [16928] 뱀과 사다리 게임 (0) | 2022.08.24 |
백준 [11559] Puyo Puyo (0) | 2022.08.23 |
백준 [2644] 촌수계산 (0) | 2022.08.23 |