[JAVA] 백준 14501번 : 퇴사

14501번: 퇴사

문제

- N+1일째 되는 날 퇴사

- 남은 N일 동안 최대한 많은 상담을 함

- 각각의 상담은 상담을 완료하는데 걸리는 기간 : Ti

- 상담을 했을 때 받을 수 있는 금액 : Pi

 

이때 얻을 수 있는 최대 수익을 구하는 프로그램

 

- N = 7인 경우에 다음과 같은 상담 일정표

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다.

5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

 

입력

- 첫째 줄에 N (1 ≤ N ≤ 15) 주어짐

- 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어짐

- 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

 

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력

 

풀이

N+1일째 퇴사 -> N일동안 하루에 하나씩 상담이 있고 일을 i로 주면

Ti : 상담을 완료하는데 걸리는 시간(일) ->t[]

Pi : 상담을 완료했을 때 받는 금액 -> p[] 

 

그리고 n일까지 일했을 때 얻을 수 있는 최대 이익을 dp[]에 넣어준다.

 

나는 처음에 N이 7이면 t[7]=1. T[6]=2, T[5]=3 … 같이 i+t[i]-1=7인 경우를 구해 그 값을 더하는 방법을 떠올렸다.

7째날에 상담기간이 1일이면, 6일까지의 최대 이익+7일에 일함으로 써 얻는 이익을 더해주는 식이었다.

즉,

t[7]=1인 경우, dp[7]=dp[7]+p[7]

t[6]=2인 경우, dp[7]=dp[6]+p[6]

t[5]=3인 경우, dp[7] =dp[5]+p[5]

 

i+t[i]-1=7 인 경우, dp[i+t[i]-1] = dp[i] + p[i] 

 

그리고 나는 N값이 무엇인지에 따라 if문을 사용했기 때문에 2중 for문을 사용했는데, 사실 생각해보면 어떤 n값이든 모든 경우를 구하게 되기 때문에 굳이 복잡하게 2중 for문까지 사용하면서 if문을 줄 필요가 없었다.

그래서 if문을 빼고, 바로 dp[i+t[i]]의 값을 계산해 저장하도록 바꿨다.

 

dp[i+t[i]-1]는 현재날짜+상담완료일을 더한 날의 이익을 구하는 것이기 때문에 dp[i], 즉 i일까지의 일했을때의 최대이익을 따로 계산해서 출력해줘야한다. 이를 max값에 저장하고 매번 max함수를 통해 그 값을 최대값으로 갱신해준다.

 

public class bj14501 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt(); // 남은 일기간
		
		int t[] = new int[n+5]; // 상담을 완료하는데 걸리는 시간
		int p[] = new int[n+5]; // 상담을 마쳤을때 받는 금액
		for(int i=1;i<=n;i++) {
			t[i] = s.nextInt();
			p[i] = s.nextInt();
		}

		int dp[] = new int[n+5]; // 얻을 수 있는 최대이익
		int max=0;
		

		for(int i=1;i<=n;i++) {
			dp[i] = Math.max(dp[i], max); // i일까지 일했을 최대이익값으로 dp[i]도 새로 갱신해줌
			dp[i+t[i]-1] = Math.max(dp[i+t[i]-1], dp[i]+p[i]);
			max = Math.max(max, dp[i]); // i일까지 일했을 때 최대이익
		}
		
		System.out.println(max);
		s.close();
	}

}

------

제출했는데 틀렸다고 떠서 수정함..

dp[i+t[i]-1]에 저장하게 했는데 -1을 빼주고 for문을 n+1까지 돌아가도록했다..

이랬는데 런타임 에러가떠서 또 이것저것 만져보는데

배열 t,p,dp의 크기를 n+5에서 10으로 늘려주니 맞았다고 뜬다.... 사실 이유는 모르겟다..

public class bj14501 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt(); // 남은 일기간
		
		int t[] = new int[n+10]; // 상담을 완료하는데 걸리는 시간
		int p[] = new int[n+10]; // 상담을 마쳤을때 받는 금액
		for(int i=1;i<=n;i++) {
			t[i] = s.nextInt();
			p[i] = s.nextInt();
		}

		int dp[] = new int[n+10]; // 얻을 수 있는 최대이익
		int max=0;
		
		for(int i=1;i<=n+1;i++) { // n+1일까지 구하는 이유는 마지막날+1일일경우까지 구해야해서
			dp[i] = Math.max(dp[i], max); // i일까지 일했을 최대이익값으로 dp[i]도 새로 갱신해줌
			dp[i+t[i]] = Math.max(dp[i+t[i]], dp[i]+p[i]);
			max = Math.max(max, dp[i]); // i일까지 일했을 때 최대이익
		}
		
		System.out.println(max);
		s.close();
	}

}