[Kotlin, G5] 백준 1011번 Fly me to the Alpha Centauri

출처: unsplash.com

 

Fly me to the Alpha Centauri(1011번)

Gold 5

#수학

 

문제 내용

 

문제 접근

수학적으로 접근하면 반복문을 사용하지 않고도 문제를 해결할 수 있다.

먼저 장치가 작동하는 횟수를 기준으로 거리와 최댓값을 확인하면 다음과 같다.

사진 1-1

이 표를 보면 3가지의 규칙을 확인할 수 있다.

1. 최댓값이 증가하면서 2번씩 반복된다.

2. 거리는 이전의 거리에서 현재의 최댓값을 더한 값과 같다.

3. 최댓값이 변하는 지점은 항상 최댓값의 제곱 값이다.

 

사진 1-1의 표를 이용해 거리의 사이에 존재하는 데이터들의 값들도 표로 나타내 보자.

분량 문제상 거리가 8부터 16까지의 데이터들에서 최댓값과 장치 작동 횟수를 구해 보겠다.

사진 1-2

녹색이 최댓값이 변하는 구간, 노란색이 작동 횟수가 변하는 구간이다.

녹색의 경우는 위에서 최댓값의 제곱이 되는 값에서 변한다고 언급했으니 넘어가고,

노란색 수의 경우에는 변하는 주기가 최댓값의 수만큼 수가 늘어나고 나서 값이 변한다는 것을 알 수 있다.

9부터 16 사이에 있는 6개의 수에서 최댓값인 3씩 장치 작동 횟수가 유지되다가 최댓값이 늘어난다는 것을 볼 수 있다.

다른 부분에서도 똑같은 규칙이 적용된다.

 

정리해 보면

1. 최댓값은 거리에서 루트를 씌운 값에서 소수점을 버린 값과 같다.

2. 최댓값이 변하는 지점 사이에서는 장치 작동 횟수의 변경이 무조건 2번 이루어진다.

3. 녹색 칸 다음에는 반드시 작동 횟수가 늘어난다(녹색 칸에 해당되는 수인 9를 예로 들면 문제의 규칙을 만족하면서 이동할 수 있는 최대의 경우이기 때문이다).

4. 두 번째 장치 작동 횟수가 변하는 시점은 첫 번째로 장치 작동 횟수가 변한 시점에서 최댓값만큼 더한 경우이다.

 

위 규칙들을 이용해 문제를 해결해 보자.

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.sqrt

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()

    for (i in 0 until case) {
        val (start, end) = readLine().split(" ").map { it.toInt() }
        val distance = end - start
        val max = sqrt(distance.toDouble()).toInt()

        if (max.toDouble() == sqrt(distance.toDouble())) println(max * 2 - 1)
        else if (distance in max * max + 1 .. (max * max) + max) println(max * 2)
        else println(max * 2 + 1)
    }
}

 

문제 풀이

시작점(start)과 종료 지점(end)의 거리 차를 distance로 구한다.

그다음 distance의 최댓값을 루트(sqrt)를 씌우고 소수점을 버려서 구해 준다.

 

<첫 번째 조건>

if (max.toDouble() == sqrt(distance.toDouble())) println(max * 2 - 1)

우선 첫 번째 조건으로는 distance가 제곱수인지 확인해줘야 한다.

max를 double로 변환한 값이 현재 distance의 루트에서 소수점을 제거하지 않은 값과 같은지 확인한다.

제곱수인 경우인 9를 예로 설명하자면

기존에 루트를 씌워 구한 max(3)에 현재 distance의 루트를 씌운 값( √distance = 3.0)이 서로 같다.

첫 번째 조건을 만족한다면 문제 접근의 1번 조건을 만족하므로 장치 작동 횟수는 max * 2 - 1가 된다.

 

<두 번째 조건>

첫 번째 조건으로 distance가 제곱수인 경우를 구했으므로 제곱수의 사이에 있는 수의 경우를 구해야 한다.

위에서 사용한 사진을 다시 불러와서 봐보겠다.

사진 1-3

위 표에서 빨강, 파랑으로 묶인 부분의 개수가 현재 최댓값과 같은 것을 알 수 있다.

그러면 현재 빨간색 부분의 조건은 다음과 같을 것이다.

max^2 < distance <= max^2 + max

위 조건을 Kotlin으로 변형하면 다음과 같은 조건이 나오게 된다.

else if (distance in max * max + 1 .. (max * max) + max) println(max * 2)

그러면 작동 횟수는 max * 2가 될 것이다.

 

<세 번째 조건>

첫 번째, 두 번째 조건에 부합하지 않으면 자동으로 나머지 distance인 경우가 될 것이다(사진 1-3의 파랑으로 묶인 부분).

(사진 1-3의 표에서 13~15에 해당)

작동 횟수는 max * 2 + 1이 된다.

else println(max * 2 + 1)

 

이렇게 3가지의 조건만 확인하면 반복문을 쓰지 않아도 모든 distance의 경우의 수를 구해서 정확한 거리를 확인해 볼 수 있다.

 

 

문제 해결 과정

처음에 문제를 접하고 풀었을 때는 완전히 잘못 접근해서 풀어서 정답이 제대로 나오지 않았다.

재귀를 이용해 처음과 끝은 무조건 1로 시작하니까 처음과 끝의 값을 하나씩 늘려 가면서 값을 구하려고 했지만 구하기가 쉽지 않았다.

결국 풀이법을 검색해서 공부해 보고 내 방식대로 글로 작성해 주었다.

내가 공부한 블로그 포스팅을 링크로 남겨 놓겠다(내가 이해하는 데 많은 도움이 되었다)

https://st-lab.tistory.com/79

[백준] 1011번 : Fly me to the Alpha Centauri - JAVA [자바]