퇴사14501

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

어떻게 풀어야 할지 감이 오지 않아서 결국 풀이를 보았고 이해가 되지 않아서 한참 고민하다 풀었다

1)뒤에서 부터 계산해야 한다는것
2)임금합계 배열을 만들어서 해결할 수 있다는 것을 깨닫기 까지 너무 오래걸렸다..

import java.io.*;

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[][] work = new int[N+2][2];

        String[] input;
        for(int i = 1; i <= N; ++i)
        {
            input = br.readLine().split(" ");
            work[i][0] = Integer.parseInt(input[0]);//T 시간
            work[i][1] = Integer.parseInt(input[1]);//P 돈
        }

        int[] money = new int[N+2];
        for(int i = N; i >= 1; --i)
        {
            if(i + work[i][0]-1 > N)//일하면 마무리를 못하는 경우
            {
                money[i] = money[i+1];
            }
            else if(work[i][0] == 1)//하루만에 끝나는 일
            {
                money[i] = money[i+1] + work[i][1];
            }
            else
            {
                //예를들어 총7일 기간(N=7). 오늘2일차 5일 걸리는일이면 6일차에 마무리하고 7일차 부터 일할 수 있다
                //그것은 2일차 임금 + 7~N 일차까지임금 합계  VS  3~N 일차까지 임금합계 의 대결이다!
                if(money[i + work[i][0]] + work[i][1] > money[i+1])
                {
                    money[i] = money[ i+ work[i][0]] + work[i][1];
                }
                else
                    money[i] = money[i+1];
            }
        }

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