백준 26645 번
https://www.acmicpc.net/problem/26645

문제

---

생각하기

---

• DFS의 방식으로 완탐을 해서 문제를 풀었다.
  • 더 쉽게 풀 수 있겠지만, 그냥 생각나는게 이 방식이었음

동작

private fun DFS(index: Int, step: Int) {

    if (step < 3) {
        if (N <= 209 && step + 1 == 1) {
            val temp = N + 8
            var level = 0
            if (temp > 210) {
                level = N + (210 - N)
            } else {
                level = temp
            }

            if (maxLevel < level) {
                maxLevel = level
                ans = Math.max(ans, 1)
            }
        } else if (N <= 219 && step + 1 == 2) {
            val temp = N + 4
            var level = 0
            if (temp > 220) {
                level = N + (220 - N)
            } else {
                level = temp
            }

            if (maxLevel <= level) {
                maxLevel = level
                ans = Math.max(ans, 2)
            }
        } else if (N <= 229 && step + 1 == 3) {
            val temp = N + 2
            var level = 0
            if (temp > 230) {
                level = N + (230 - N)
            } else {
                level = temp
            }

            if (maxLevel <= level) {
                maxLevel = level
                ans = Math.max(ans, 3)
            }
        }
    } else {
        return
    }

    for (i in index until 3) {
        DFS(i + 1, step + 1)
    }
} // End of solution

각 단계별로 최적의 성장비약을 구하는 문제이다.

한번 생각해봐야 하는 부분이 레벨이 207이라고 가정했을 때,
1번 성장의 비약을 사용하면 레벨을 최대 210까지 올릴 수 있지만,
2번 성장의 비약을 사용한다면 211까지 레벨을 올릴 수 있으므로 여기서 최적의 선택은 2번을 선택하는 것이다.

이런 상황을 대처하기 위해서 나는 DFS 방식을 통해서 완탐을 선택했다

1번 비약을 선택했을 때 최대 레벨은 어디인지 계산하고,
2번 비약을 선택했을 때 최대 레벨은 어디인지 계산, 또 3번으로 계산 등을 해서

가장 높은 레벨의 값을 가지는 비약을 선택하면 정답을 찾을 수 있다.

// 1을 선택했을 때는 최대 몇 까지 갈 수 있나
// 2를 선택했을 때는 최대 몇 까지 갈 수 있나
// 3을 선택했을 때는 최대 몇 까지 갈 수 있나

코드

---

Kotlin

import java.io.*

private var maxLevel = 0
private var N = 0
private var ans = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    N = br.readLine().toInt()
    if (N >= 229) {
        println(4)
        return
    }

    DFS(0, 0)
    println(ans)
} // End of main

// 1을 선택했을 때는 최대 몇 까지 갈 수 있나
// 2를 선택했을 때는 최대 몇 까지 갈 수 있나
// 3을 선택했을 때는 최대 몇 까지 갈 수 있나
private fun DFS(index: Int, step: Int) {

    if (step < 3) {
        if (N <= 209 && step + 1 == 1) {
            val temp = N + 8
            var level = 0
            if (temp > 210) {
                level = N + (210 - N)
            } else {
                level = temp
            }

            if (maxLevel < level) {
                maxLevel = level
                ans = Math.max(ans, 1)
            }
        } else if (N <= 219 && step + 1 == 2) {
            val temp = N + 4
            var level = 0
            if (temp > 220) {
                level = N + (220 - N)
            } else {
                level = temp
            }

            if (maxLevel <= level) {
                maxLevel = level
                ans = Math.max(ans, 2)
            }
        } else if (N <= 229 && step + 1 == 3) {
            val temp = N + 2
            var level = 0
            if (temp > 230) {
                level = N + (230 - N)
            } else {
                level = temp
            }

            if (maxLevel <= level) {
                maxLevel = level
                ans = Math.max(ans, 3)
            }
        }
    } else {
        return
    }

    for (i in index until 3) {
        DFS(i + 1, step + 1)
    }
} // End of solution