[백준 19947번] 투자의 귀재 배주형 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

이번 문제는 DP를 이용하여 풀어보았습니다.

 

이자는 투자기간이 끝나는 시점에 얻을 수 있다고 하였습니다. 또한 투자 방식은 매년 변경이 가능합니다.

 

여기서 투자 방식은 매년 변경이 되지만 투자기간이 끝나는 시점에 이자를 얻을 수 있으므로 한번 투자한 투자유형을 변경하는 것은 곧 이자를 0원 얻는 것이므로 투자 유형을 변경하는 것은 최고의 이자를 받을 수 있는 방법이 아닙니다.

 

만약 입력으로 투자 기간이 0이 주어진다면 가장 많은 이득을 본 금액은 투자를 시작하고자 한 금액이 될 것입니다.

 

그 말은 DP[0]의 값은 투자를 시작하고자 한 금액이 될 것입니다.

 

이번에는 입력으로 투자 기간이 3이 주어진 경우를 보도록 하겠습니다.

 

DP[0]의 경우는 최초 투자금액이 되며 투자 기간 1년인 DP[1]은 어떻게 될까요?

 

DP[0]에서 1년 투자 상품의 이율인 5%의 이율이 더해진 값이 될 것 입니다.

즉 DP[1] = DP[0] + DP[0] * 0.05 이 됩니다.

 

그럼 이번에는 투자기간이 3년이 DP[3]은 어떻게 될까요?

 

위에서 말한 1년 투자 상품에 가입한 경우 DP[3] = DP[2] + DP[2] * 0.05의 값이 될 것이며,

3년 투자 상품에 가입한 경우 DP[3] = DP[0] + DP[0] *0.2의 값이 될 것입니다.

 

위 두 결과 값 중 큰 값이 투자기간 3년이 된 시점의 가장 많은 이득을 본 금액이 될 것입니다.

즉 DP[3] = MAX(DP[0] + DP[0] *0.2, DP[2] + DP[2] * 0.05)

 

위 예시를 보면 알 수 있듯이 투자를 하고자 하는(입력으로 주어진 투자기간) 기간이 3년 이상이면 투자 가능 상품은 2개가 되고 5년 이상이면 3개가 될 것입니다.

 

그럼 3년 전 까지는 1년 상품을 가입한 경우가 최고 금액이 되면 3년 이상부터는 1년과 3년 상품 중 더 많은 이자를 주는 상품에 가입 하는 것이 최고 금액이 되며, 5년 이상이되면 1년과 3년 그리고 5년 상품 중 더 많은 이자를 주는 상품에 가입하는 것이 최고 금액이 될 것입니다.

DP[1]	DP[2]	DP[3]	DP[4]	DP[5]
DP[0] * 0.05	DP[1] * 0.05	MAX DP[2] * 0.05, DP[0] * 0.2	MAX DP[3] * 0.05, DP[1] * 0.2	MAX DP[4] * 0.05, DP[2] * 0.2, DP[0] * 0.35

DP[6]	DP[7]	DP[8]	DP[9]	DP[10]
MAX DP[5] * 0.05, DP[3] * 0.2, DP[1] * 0.35	MAX DP[6] * 0.05, DP[4] * 0.2, DP[2] * 0.35	MAX DP[7] * 0.05, DP[5] * 0.2, DP[3] * 0.35	MAX DP[8] * 0.05, DP[6] * 0.2, DP[4] * 0.35	MAX DP[9] * 0.05, DP[7] * 0.2, DP[5] * 0.35

위 표 처럼 계산이 되어야 할 것입니다.

6. 코드

전체 코드는 Git에 있습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stringTokenizer;

stringTokenizer = new StringTokenizer(br.readLine());

int pay = Integer.parseInt(stringTokenizer.nextToken());
int year = Integer.parseInt(stringTokenizer.nextToken());

long[] dp = new long[year+1];

dp[0] = pay;

for(int i=1; i<=year; i++){
	dp[i] = (long)Math.floor(dp[i-1] * 1.05);
	if(i >= 3)
		dp[i] = Math.max((long)Math.floor(dp[i-3] * 1.2), dp[i]);
	if(i >= 5)
		dp[i] = Math.max((long)Math.floor(dp[i-5] * 1.35), dp[i]);
}

bw.write(dp[year] + "\n");
bw.flush();