백준 19947 투자의 귀재 배주형 Kotlin(완전 탐색)

문제 출처 : https://www.acmicpc.net/problem/19947

19947번: 투자의 귀재 배주형

문제

2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다.

주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 

• 1년마다 5%의 이율을 얻는 투자 (A)
• 3년마다 20%의 이율을 얻는 투자 (B)
• 5년마다 35%의 이율을 얻는 투자 (C)

투자를 할 때에는 다음과 같은 주의점이 있다.

• 투자의 기한(1년, 3년, 5년)을 채우는 시점에 이율이 반영되며, 그 사이에는 돈이 늘어나지 않는다.
• 투자 방식은 매년 바꿀 수 있다.
• 매번 이율은 소수점 이하를 버림 해서 받는다.

예를 들어서, 지금 가진 돈이 11111원이면, A 방식이면 1년 후에 555원, B 방식이면 3년 후에 2,222원, C 방식이면 5년 후에 3,888원을 이자로 받을 수 있다. 만약 C 방식으로 투자했지만 4년이 지난 시점이라면 받을 수 있는 이자는 0원이다.

주형이의 초기 비용이 H원일 때, Y년이 지난 시점에 가장 많은 금액을 얻을 수 있는 투자 패턴을 분석하고 그 금액을 출력하자.

입력

첫째 줄에 초기 비용 H와 투자 기간 Y가 주어진다.

모든 입력은 정수로 주어진다.

출력

가장 많은 이득을 얻었을 때의 총 자산을 소수점을 모두 버리고 정수로 출력한다.

제한

• 10,000 ≤ H ≤ 100,000, H는 정수
• 0 ≤ Y ≤ 10, Y는 정수

알고리즘 분류

• 다이나믹 프로그래밍
• 브루트포스 알고리즘
• 재귀

풀이

간단한 완전 탐색 문제이다. 근데 이제 실수 연산을 곁들인.

투자의 기한(1년, 3년, 5년)을 채우는 시점에 이율이 반영되며,그 사이에는 돈이 늘어나지 않는다.
투자 방식은 매년 바꿀 수 있다.
매번 이율은 소수점 이하를 버림 해서 받는다.

문제 조건을 읽어보면, 만약 y가 8이라고 할 때, A + B + C 가 가능하다.

따라서 A,B,C를 가지고 y년을 만들 수 있는 모든 조합을 구해 비교해봐야 한다.

이는 dfs로 쉽게 구할 수 있다.

 

68% 쯤에서 틀린다면 소수 연산 후 캐스팅에서 오차가 발생한 것인데,

h+(h*0.05).toInt()가 아닌 

(h+(h*0.05)).toInt() or (h*1.05).toInt()
이런 식으로 해주면 통과한다.

 

그나저나 엊그제 내 스트릭이 깨졌다..

충격받고 일요일도 백준을 풀지 않았다.

요즘 swea를 풀어서 그런 것도 있지만, 그저께 프로젝트하느라 문제 푸는 것을 완전히 잊고 있었다.

다시 초심으로 돌아가서 달리자!

코드

val br = System.`in`.bufferedReader()
var answer=0

fun dfs(h: Int, y: Int){
    if(y==0){
        answer = answer.coerceAtLeast(h)
        return
    }
    if(y-1>=0){
        dfs((h*1.05).toInt(),y-1)
    }
    if(y-3>=0){
        dfs((h*1.2).toInt(),y-3)
    }
    if(y-5>=0){
        dfs((h*1.35).toInt(),y-5)
    }
}

fun main() = with(System.out.bufferedWriter()){

    val (h,y) = br.readLine().split(' ').map{it.toInt()}
    dfs(h,y)
    write("$answer")
    close()
}