백준 14501 퇴사(Java)

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

14501번: 퇴사

---

 

해석 및 팁

 

---

 

이 문제는 먼저 배열에 값을 입력받은 후 뒤에서부터 비교하여 최댓값을 찾아내면 됩니다. 다만 날짜와 상담일의 합이 n+1보다는 크면 안 된다.

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
  
    int n = sc.nextInt();
    int[] sum = new int[n+6];
    int[][] arr = new int[n+6][2];

    for(int i = 1; i <= n; i++) {
      arr[i][0] = sc.nextInt();     //시간
      arr[i][1] = sc.nextInt();     //돈
    }

    for(int i = n; i > 0; i--) {
      if(i + arr[i][0] <= n + 1) sum[i] = Math.max(sum[i + 1], sum[i + arr[i][0]] + arr[i][1]);
      else sum[i] = sum[i + 1];
    }

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