[백준] 14501번: 퇴사 [C#]

예제가 많아서 주요한 예제 하나만 들고왔습니다

단순한 다이나믹 프로그래밍 처럼 보이지만, 브루트포스의 성질도 띄고있는 문제입니다.

단순히 n일 후의 이익만 계산하면 안되고,  n + a의 이익도 계산해서 최대의 값을 구해야 하는 문제입니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    internal class _14501_boj
    {
        public void boj_14501()
        {
            int N = int.Parse(Console.ReadLine());
 
            int[] dp = new int[N + 1];
            int[] time = new int[N + 1];
            int[] value = new int[N + 1];
 
            for (int i  = 1; i < dp.Length; i++)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                time[i] = input[0];
                if (i + time[i] <= dp.Length)
                    value[i] = input[1];
                else
                    value[i] = 0;
            }
 
            for (int i = 1; i < dp.Length; i++)
            {
                dp[i] = Math.Max(dp[i], value[i]);
                for (int j = i + time[i]; j < dp.Length; j++)
                { 
                    if (j < dp.Length)
                    {
                        dp[j] = Math.Max(dp[j], dp[i] + value[j]);
                    }
                }
            }
            
            Console.WriteLine(dp.Max());
        }
    }
}
 

 

for문을 한번만(i for문) 돌렸을 때는, 위의 예제에서 출력이 80이 나왔다.

6일차까지 상담을 들어 60의 이익을 얻고, 바로 2일치 상담을 들어 80이 최고 이익이라는 결과가 나왔기 때문이다.

하지만 문제의 정답은 90이다. 즉, 7일차의 20짜리 상담을 포기하고, 8일차의 30짜리 상담을 들어야지 올바른 값을 얻을 수 있다는 것이다.

이것을 구현하기 위해서 for문을 한개 더 만들어 j일(여기서는 6일)부터 퇴사일까지 모든 상담의 이익을 비교해서 가장 큰 이익을 얻어주었다.