[코딩테스트][다이나믹프로그래밍][Java] 백준 14501, 퇴사

1. 문제

 

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

14501번: 퇴사

 

2. 접근

위의 예제에서 1일에 상담을 수행하면 총 3일이 소요되며 상담을 시작하는 날 포함하여 3일까지는 다른 상담을 수행할 수 없습니다. 만약 3일에 상담을 수행하면 3일 당일에 상담을 완수하고 10원을 받을 수 있습니다. 위의 예제에서 퇴사전에 받을 수 있는 최대 이익은 1일, 4일, 5일에 상담을 수행하고 총 45원을 받는 것입니다.

 

여기서 주목할 점은 7일까지 전부 상담을 마치고 8일날 퇴사를 하게 되는데 8일날에 45원을 받는다는 점입니다. 예를 들어 3일날 일을하고 당일에 상담을 완료하였다고 바로 10원을 받는것이 아닌 그 다음날이 4일에 받습니다. 그리고 어느 특정일날 상담을 수행하게 되면 상담을 완료날까지는 다른 상담을 맡을 수 없기 때문에 점화식은 다음과 같이 표현할 수 있습니다.

 

dp[today] = 1일~(today-1)일날까지 상담을 해서 받을 수 있는 최대이익

 

수행과정은 1번째부터~N번째까지 수행이 되는데 여기서 고려할점은 today일날 일을 하는 경우와 일을 하지 않는 경우로 나누어집니다. 일을 하는 경우는 today날 상담을 진행하여 완료해도 퇴사일의 범위 안쪽에 있는 경우입니다. 일을 하지 않는 경우는 today날 상담을 진행하지 않고 다음날들에 상담을 진행하여 더 많은 보수를 바라는 경우입니다. 

 

따라서 today일날 일을 하는 경우의 최대이익과 일을 하지 않는 경우를 모두 고려하여 dp 배열에 최대값을 넣어야 합니다.

 

1일날 일을 하는 경우

예를 들어 1(today)일날 상담을 수행하면 3일날 상담이 완료되고 4일날(1일~3일날까지 상담을 해서 받을 수 있는 최대이익)에 받을 수 있는 최대이익은 10원입니다. 그렇다면 점화식은 다음과 같이 표현할 수 있습니다.

dp[today+T[today]] = dp[today] + p[today];
today = 1;
dp[4] = dp[1] + p[1];

위와 같이 4일날 받을 수 있는 최대이익은 1일날 받을 수 있는 최대이익 + 1일날 상담보수금액 입니다.

 

2일날 일을 하는 경우

2일날 일을 수행하면 마찬가지로 7일날 받을 수 있는 최대이익은 20원입니다.

 

위와 같은 방식으로 1일날부터 7일날까지 일을 할 수 있는 경우(today일날+상담소요일<퇴사일)에 상담 완료 다음날에 받을 수 있는 최대 이익을 저장합니다.

 

일을 하지 않는 경우

일을 하는 경우와 마찬가지로 1일날부터 7일날까지 일을 하지 않는 경우의 최대이익도 고려해야 합니다. 만약 today날 일을 하지 않는다면 today+1일날은 today날 받을 수 있는 최대이익과 동일할 것입니다. 이를 점화식으로 표현하면 다음과 같습니다.

dp[today+1] = dp[today];

 

최대 이익값 탐색

위와 같이 배열을 순회하면서 일을 하는경우와 일을 하지 않는 경우의 최대이익을 dp 배열에 저장하기 전에 기존 dp 배열의 값과 비교하여 최대값을 저장하여야 합니다. 최대값을 비교하는 부분을 점화식으로 표현하면 아래와 같습니다.

// 일을 하는 경우 최대이익 저장
// dp[today+t[today]] : 기존 today+t[today]일날 최대이익
// dp[today]+p[today] : (1~today-1)일날 받는 최대이익 + today일날 상담보수
dp[today+t[today]] = Math.max(dp[today+t[today]], dp[today]+p[today]);

// maxMoney : 퇴사일날 받는 최대이익
maxMoney = Math.max(maxMoney, dp[today+t[today]]);

일을 하지 않는 경우도 일을 하는 경우와 마찬가지로 today일날 받을 수 있는 최대이익을 그대로 이월하지 않고 기존 today+1일날 받을 수 있는 최대이익과 비교하여 최대값을 dp[today+1]에 저장해야 합니다. 이를 점화식으로 표현하면 아래와 같습니다.

// 일을 하지 않는 경우
dp[today+1] = Math.max(dp[today+1], dp[today]);

// 최대값 갱신
maxMoney = Math.max(maxMoney, dp[today+1]);

 

3. 구현

public class Main {
	private static int[] t;
	private static int[] p;
	private static int[] dp;

	public static int solution(int n)
	{
		int maxMoney=0;
		
		for(int i=1;i<=n;i++)
		{
			// 1) i번째 날에 일을 했을 경우
			if(i+t[i]<=n+1)
			{
				dp[i+t[i]] = Math.max(dp[i+t[i]], dp[i]+p[i]);
				
				// 최대값 갱신
				maxMoney= Math.max(maxMoney, dp[i+t[i]]);
			}
			
			// 2) i번째 날에 일을 하지 않은 경우
			dp[i+1] = Math.max(dp[i+1], dp[i]);
			
			// 최대값 갱신
			maxMoney= Math.max(maxMoney, dp[i+1]);
		}
		return maxMoney;
	}
	
	public static int solution2(int today, int n, int maxMoney)
	{
		if(today>n)
		{
			return maxMoney;
		}
		// 일을 할 수 있는 경우
		if(today+t[today]<=n+1)
		{
			dp[today+t[today]] = Math.max(dp[today+t[today]], dp[today]+p[today]);
			
			//최대값 갱신
			maxMoney = Math.max(maxMoney, dp[today+t[today]]);
		}
		
		// 일을 하지 않는 경우
		dp[today+1] = Math.max(dp[today+1], dp[today]);
		
		// 최대값 갱신
		maxMoney = Math.max(maxMoney, dp[today+1]);
		
		return solution2(today+1, n, maxMoney);	
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());	// 일수
		int nMaxCount = 17;
		dp = new int[nMaxCount];	// n일을 기준으로 받을 수 있는 최고 보수
		t = new int[nMaxCount];	// 상담 일수
		p = new int[nMaxCount];	// 보수 금액
		
		for(int i=1;i<=n;i++)
		{
			String[] str = br.readLine().split(" ");
			t[i] = Integer.parseInt(str[0]);
			p[i] = Integer.parseInt(str[1]);
		}
		System.out.println(solution2(1,n,0));
	}
}

 

References

https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-14501-%ED%87%B4%EC%82%AC-exjyfr5vgj
https://mygumi.tistory.com/151