백준 - 태권왕(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

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

 

[문제 설명]

태균이의 점수와 상대방의 점수가 같아지려면 몇 번 태균이가 발차기를 성공해야 하나요?

 

[접근 방법]

1번 발차기는 자신의 점수*2와 상대방의 점수 +3을 해준다.

2번 발차기는 자신의 점수를 +1한다.

 

처음에는 과연 규칙이 있을까를 먼저 생각해봤다.

내가 생각할 수 있는 방법 중에는 없어보인다.

 

그렇다면 완전탐색으로 제한 시간 내에 풀 수 있는 문제인가를 생각해봤다.

케이스의 수는 C, 두 사람의 점수차는 T-S.

최악의 경우에도 100*2^7*100보다 작을 것으로 보인다. 128만으로 여유롭다.

따라서 재귀를 이용한 완전 탐색으로 풀었다.

 

[Kotlin 코드]

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cntOfTestcase = readLine().toInt()
    repeat(cntOfTestcase) {
        val (S,T) = readLine().split(" ").map { it.toInt() }
        println(getMinKickCnt(currentKickCnt = 0, scoreOfTaeGyun = S, scoreOfEnemy = T))
    }
}

fun getMinKickCnt(currentKickCnt: Int, scoreOfTaeGyun: Int, scoreOfEnemy: Int): Int {
    // 태균이의 점수가 더 커지면 불가능하므로 정수의 최대값을 리턴
    if (scoreOfTaeGyun > scoreOfEnemy) {
        return Int.MAX_VALUE
    } else if (scoreOfTaeGyun == scoreOfEnemy) {
        // 두 사람의 점수가 같아지면 찬 회수를 리턴
        return currentKickCnt
    }

    // 둘 중 작은 값을 리턴
    return getMinKickCnt(currentKickCnt+1, scoreOfTaeGyun*2, scoreOfEnemy+3).coerceAtMost(getMinKickCnt(currentKickCnt+1, scoreOfTaeGyun+1, scoreOfEnemy))
}