[14501] 퇴사

✔ 퇴사

[백준 14501]

문제 분석하기

i번째 날부터 퇴사일까지 벌 수 있는 최대 수입으로 D[i]를 정의해 동적 계획법을 실행

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[i]는 i번째 날부터 퇴사날까지 벌 수 있는 최대 수입
2. 점화식을 구함
   • 오늘 시작되는 상담을 했을 때 퇴사일까지 끝나지 않는 경우인 D[i] = D[i + 1]
   • 오늘 시작되는 상담을 했을 때 퇴사일 안에 끝나는 경우인 D[i] = Max(D[i + 1], D[i + T[i]] + P[i])
3. 점화식으로 D 배열을 채운 후 D[1]의 값을 출력

슈도코드 작성하기

D(점화식 배열 -> i ~ 퇴사일까지 벌 수 있는 최대 수입을 저장하기)
T(상담에 필요한 일 수 저장 배열)
p(상담을 완료했을 때 받는 수입 저장 배열)
for(N만큼 반복하기) {
    T와 P 배열 입력받기
}
for(i -> N ~ 1까지 반복하기) {
    if(i + T[i] > N + 1) {
        D[i] = i + 1일 ~ 퇴사일까지 벌 수 있는 최대 수입
    }
    else {
        D[i] = MAX(i + 1일 ~ 퇴사일에 벌 수 있는 최대 수입과 i번째 상담 비용 + i번째 상담이 끝난 다음 날부터 퇴사일까지의 최대 수입)
    }
}
D[1](1일부터 퇴사일까지 벌 수 있는 최대 수입) 출력하기

코드 구현하기

/**
 * 14501) 퇴사
 */
public class D085_14501 {
    static int N;
    static int D[];
    static int T[];
    static int P[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        // D(퇴사일까지 벌 수 있는 최대 수입을 저장하기)
        D = new int[N + 2];
        // T(상담에 필요한 일 수 저장 배열)
        T = new int[N + 1];
        // p(상담을 완료했을 때 받는 수입 저장 배열)
        P = new int[N + 1];
        // T와 P 배열 입력받기
        for (int i = 1; i <= N; i++) {
            T[i] = sc.nextInt();
            P[i] = sc.nextInt();
        }
        for (int i = N; i > 0; i--) {
            // i번째 상담을 퇴사일까지 끝낼 수 없을 때
            if (i + T[i] > N + 1) {
                // i + 1일 ~ 퇴사일까지 벌 수 있는 최대 수입
                D[i] = D[i + 1];
            }
            // i번째 상담을 퇴사일까지 끝낼 수 있을 때
            else {
                // MAX(i + 1일 ~ 퇴사일에 벌 수 있는 최대 수입과 i번째 상담이 끝난 다음 날부터 퇴사일까지의 최대 수입 + i번째 상담 비용)
                D[i] = Math.max(D[i + 1], D[i + T[i]] + P[i]);
            }
        }
        // D[1](1일부터 퇴사일까지 벌 수 있는 최대 수입) 출력하기
        System.out.println(D[1]);
    }
}