1011번: Fly me to the Alpha Centauri

문제 풀이 아이디어

풀이 전략

1. 이동 횟수별 최대 이동거리를 구하고
2. x와 y 사이의 거리에 맞추어 최소 이동횟수를 구합니다.

규칙성 찾기 = 직접 적어보는게 최고!

이동 횟수별 최대 이동거리를 구해봅니다. (처음은 무조건 1, 끝도 무조건 1)
1회: 1 = 1
2회: 1 1 = 2
3회: 1 2 1 = 4
4회: 1 2 2 1 = 6
5회: 1 2 3 2 1 = 9
6회: 1 2 3 3 2 1 = 12
7회: 1 2 3 4 3 2 1 = 16

규칙성

1씩 증가하는 등차수열을 가운데를 기준으로 2개를 펼쳐놓은 모습입니다.

• 홀수/짝수가 규칙성이 다릅니다.

= 등차수열의 합 공식 = n * (n + 1) / 2을 활용하면 쉽게 규칙성을 도출할 수 있습니다.

1. 짝수일 때 규칙
   2n회 이동할 때 최대 거리
   = (1 ~ n의 합) 2
   = n (n + 1)
2. 홀수일 때 규칙
   (2n + 1)회 이동할 때 최대 거리
   = (1 ~ n의 합) 2 + (n + 1)
   = n (n + 1) + (n + 1)
   = (n + 1)^2

코드

let T = Int(readLine()!)!

(0..<T).forEach { _ in
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let x = input[0]
    let y = input[1]
    let distance = y - x
    var n = 0
    
	// n을 0부터 증가시키면서 2n일 경우, 2n + 1일 경우의 이동거리와 비교합니다.
    while true {
        if distance <= n * (n + 1) {
            print(2 * n)
            break
        } else if distance <= (n + 1) * (n + 1) {
            print(2 * n + 1)
            break
        } else {
            n += 1
        }
    }
}

(참고) 제곱과 제곱근

제곱

이 문제의 코드의 중간에는 제곱을 구하기 (n + 1) * (n + 1)의 방식으로 그냥 두 수를 무식하게(?) 곱해준 모습입니다. 사실 Swift에도 제곱을 구하는 함수가 있습니다만 Int를 인자로 받지 않고 Decimal 타입을 받기 때문에 Double이나 Float로 변환한 뒤 Int로 다시 변환해서 출력해야 하는 번거로운 과정을 거칩니다.

위 풀이에서는 제곱만 필요하므로 그냥 풀어서 사용했습니다만 다른 문제 풀이에서는 세제곱, 네제곱, ... 그 이상이 필요할 수도 있습니다. 그 경우에는 pow라는 아래 제곱을 구하는 함수를 사용하면 됩니다.

아래 풀이는 pow를 사용해서 위 문제를 푼 것입니다. (참고로 pow는 Foundation을 import 해야 사용 가능합니다.)

import Foundation

let T = Int(readLine()!)!

(0..<T).forEach { _ in
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let x = input[0]
    let y = input[1]
    let distance = Double(y - x) //👉 크기 비교를 위해 Double로 변환
    var n = 0.0 //👉 소수점을 붙여 Double로 선언

    while true {
        if distance <= n * (n + 1) {
            print(Int(2 * n)) // 👉 Int로 다시 변환해서 출력
            break
        } else if distance <= pow(n + 1, 2) {
            print(Int(2 * n + 1))
            break
        } else {
            n += 1
        }
    }
}

제곱근

제곱근을 구하는 함수는 square root의 줄임말인 sqrt입니다. pow와 마찬가지로 Double이나 Float만을 인자로 받으며 Foundation 프레임워크를 import해야 합니다.

import Foundation

let n = 25.0 //👉 Double이나 Float
let rootN = sqrt(n) // = 5.0