[다이나믹] BOJ#14501 - 퇴사

[ye-yo]

⚠️ 나의 풀이

오늘 일자에 상담을 하는 경우와 하지 않는 경우 중 max값을 저장하려고 함.

❗️ 오답 원인 분석

• 각 일자별 상담종료일자(상담기간)를 어떻게 고려할지 생각해보아야 함.

🔑 풀이 핵심

• dp[i] = max(P[i] + dp[end],dp[i+1])
• 점화식에 맞춰서 배열 크기 잡기

 for(int i= N; i>0; i--){
        int end = T[i] + i;
        if(T[i] + i - 1 > N) dp[i] = dp[i+1]; //만료일자가 N보다 크면 안됨
        else dp[i] = max(P[i] + dp[end],dp[i+1]);
    }

예를 들어 5일차는 소요일수가 2일. 2일 소요되면 6일차 일을 진행못함
=> 5일차 일을 진행했을 경우 vs 5일차 일을 하지 않고 6일차 일을 진행했을 경우
=> 5일차 일을 진행했을 경우 = 5일차 일을 진행한 금액 + 5일차 일이 종료되는 날에 일을 진행했을 경우
=> max(dp[i+1], P[i] + dp[end]);