[Java] 백준 - 14501번: 퇴사

11월 6일(월) - 다이나믹 프로그래밍 (14501번)

14501번: 퇴사

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. time, pay, dp 배열의 크기를 설정하는 과정에서 ArrayIndexOutOfBoundsException 이 발생

-> time 과 pay의 크기는 N+1에서 부족할 이유가 없음

-> dp의 크기를 N+2개로 늘렸더니 해결

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(C언어 풀이 활용)

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

import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] time = new int[N+1];
        int[] pay = new int[N+1];
        int[] dp = new int[N+2];

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

            time[i] = Integer.parseInt(st.nextToken());
            pay[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=N; i>0; i--)
        {
            int dead_line = i + time[i];

            if(dead_line <= N+1)
            {
                dp[i] = Math.max(dp[i+1], dp[dead_line] + pay[i]);
            }
            else
            {
                dp[i] = dp[i+1];
            }
        }

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ