백준 15486번 - 퇴사 2

장근영·2024년 8월 26일
0

BOJ - DP

목록 보기
21/39

문제

백준 15486번 - 퇴사 2


아이디어

  • dp[i]i번째 날부터 퇴사일(N+1일)까지 얻을 수 있는 최대 금액이라 가정해본다.
  • 그럼 i가 1일때를 구해야 하므로 N일부터 1일 순으로 결과를 도출해 나간다.
  • 현재 일수 i에서 T[i]을 더했을 때 퇴사일(N+1일)을 넘어간다면 다음 날에 얻을 수 있는 최대 금액과 같다.
  • 퇴사일을 넘어가지 않는다면 다음 날 최대 금액과 현재 일수 i에서 T[i]이 지난 후에 금액과 현재 일수에서 일했을 때 금액(P[i])을 더한 금액 중 최댓값을 저장한다.
  • 문제 예제를 기준으로 과정은 다음과 같다.
  1. 7일째에서 2일이 걸리면 퇴사일을 넘어가므로 다음 날 얻을 수 있는 최대 금액을 저장한다. (dp[i] = dp[i+1])

  1. 6일째에서 4일이 걸리면 퇴사일을 넘어가므로 다음 날 얻을 수 있는 최대 금액을 저장한다. (dp[i] = dp[i+1])

  1. 5일째에서 2일은 퇴사일을 넘어가지 않으므로 그냥 일을 안 했을 때(dp[i+1])와 일을 했을 때(dp[i+T[i]]+P[i])를 비교하여 큰 값을 저장한다.

  1. 4일째에서 1일은 퇴사일을 넘어가지 않으므로 두 값을 비교한다.

  1. 3일째에서 1일은 퇴사일을 넘어가지 않으므로 두 값을 비교한다.

  1. 2일째에서 5일은 퇴사일을 넘어가지 않으므로 두 값을 비교한다.

  1. 1일째에서 3일은 퇴사일을 넘어가지 않으므로 두 값을 비교한다.

  1. dp[1]인 45가 정답이다.
  • 참고로 1, 2, 3일의 결과가 같은 것은 최대 수익을 버는 경우의 수가 1, 4, 5일, 3, 4, 5일로 두 가지가 존재하기 때문이다.

예상 시간 복잡도

  • 예상 시간 복잡도 : O(N)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_15486 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] t = new int[n + 1];
        int[] p = new int[n + 1];
        int[] dp = new int[n + 2];

        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = n; i >= 1; i--) {
            if (i + t[i] > n + 1) {
                dp[i] = dp[i + 1];
            } else {
                dp[i] = Math.max(dp[i + 1], dp[i + t[i]] + p[i]);
            }
        }

        System.out.println(dp[1]);
    }
}

profile
오늘 할 일을 내일로 미루지 말자.

1개의 댓글

comment-user-thumbnail
2024년 8월 27일

좋은 글 잘봤습니다. 궁금한게 고용형태가 궁금하네요 ㅋㅋ 정규직은 보통 하루 8시간 근무인데 8시간
근무에 따른 시급을 적용한걸까요? 아니면 매일 급여가 달라지는 직장인을 적용한걸까요? ㅎㅎ
일급 하루 8만원? 이면 물론 시간복잡도를 퇴사일기준 급여에 대한 계산을 하신 것 같지만 ㅎㅎ

답글 달기
Powered by GraphCDN, the GraphQL CDN