Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Archives
Today
Total
관리 메뉴

차근차근

[백준 14501] 퇴사 본문

대학교/Algorithm

[백준 14501] 퇴사

SWKo 2020. 3. 7. 20:58

0. 제목

  • 백준 14501 퇴사
  • BOJ 14501 퇴사
  • C++ 14501 퇴사

1. 문제

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


2. 풀이

  • dp방식을 사용하였으며 dp배열의 원소값을 0으로 모두 초기화 하고 시작하였다.
  • 만약 일을 진행하는데 주어진 날보다 초과되면 dp[i+1] 값을 해주면 된다. 초기에 0으로 초기화해주었기 때문에 N이 초과되어도 0으로 갱신이 가능하다.
  • 주어진 날 내에 끝낼 수 있다면 dp[i] = max(dp[i+T[i]] + P[i], dp[i+1]); 을 수행해준다.
  • 위 점화식을 풀어 설명해보면 dp[i+T[i]]+P[i] 는 i번째 상담을 수행하면 T[i]일간 상담을 못하고 P[i]의 금액을 얻을 수 있고, dp[i+1]은 i번째 상담을 수행하지 않으면 그 전단계(역으로 가기 때문에 전단계라고 표현함)인 dp[i+1]으로 갱신되게 된다.
  • 그렇게 마지막 단계인 dp[1] 이 얻을 수 있는 최대 수익이 된다. 

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;
 
int N;
int T[16];
int P[16];
int dp[16];
 
int main(int argc, const char * argv[]) {
    cin >> N;
 
    for(int i = 1; i <= N; i++){
        cin >> T[i] >> P[i];
    }
    
    for(int i = N; i >= 1; i--){
        if(i + T[i] - 1 > N){
            dp[i] = dp[i + 1];
            continue;
        }
        
        dp[i] = max(dp[i + T[i]] + P[i], dp[i+1]);
    }
    
    cout << dp[1<<'\n';
    
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 11651] 좌표 정렬하기 2  (0) 2020.03.09
[백준 1003] 피보나치 함수  (0) 2020.03.08
[백준 2309] 일곱 난쟁이  (0) 2020.03.06
[백준 1931] 회의실배정  (0) 2020.03.06
[백준 1783] 병든 나이트  (0) 2020.03.06
Comments