[백준] 14501 퇴사

문제보기

import java.util.*;

public class Main {
  public static int[] T;
  public static int[] P;
  public static int n;
  public static int max = 0;

  public static void go(int day, int sum){
    // == 가 아니라 <= 란 점이 중요한데,
    // 사실 퇴사 전날까지 꽉채워서 일 안할 수도 있기 때문임
    // 걍 퇴사 전까지 만들수 있는 최대 페이만 뽑으면 되기 때문에
    // 중간중간 발생하는 최대값은 모두 전역변수 max에 저장을 합시다
    if(day <= n){
      if(sum > max){
        max = sum;
      }
    }
    // 퇴사 못하고 여전히 업무 보고 있는 것이므로 걍 종료해줍니다
    if(day > n-1){
      return;
    }
    
    //일감 안받고 내일로 넘기기
    go(day+1, sum);
    
    //일감 받고 가기 (날짜는 T만큼 건너뛰어야하고, 페이는 챙기고!)
    go(day + T[day], sum + P[day]);    
  }

  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    T = new int[n];
    P = new int[n];
    for(int i = 0 ; i < n ; i++ ){
      T[i] = sc.nextInt();
      P[i] = sc.nextInt();
    }

    go(0, 0);

    System.out.println(max);

  }
}