백준 1484번: 다이어트

문제: https://www.acmicpc.net/problem/1484

문제 풀이

투 포인터

before = 기억하고 있던 몸무게

after = 현재 몸무게

find = 가능한 현재 몸무게가 있는지 여부

diff = 현재 몸무게의 제곱에서 기억하고 있던 몸무게의 제곱을 뺀 값

몸무게 제곱의 차이를 계산했을 때 이 값이 G보다 작으면 현재 몸무게 증가, G보다 크면 기억하고 있던 몸무게 증가, 같다면 현재 몸무게 출력 후 현재 몸무게 증가

이를 현재 몸무게가 50001일때까지 반복하면 가능한 모든 현재 몸무게를 오름차순으로 출력하므로 정답

풀이 설명

G킬로그램은 성원이의 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다.

첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우는 제외해야 한다.

현재 몸무게의 제곱에서 기억하고 있던 몸무게의 제곱을 뺀 값이 정확히 G가 되도록 몸무게를 조절해야 하므로 투 포인터로 풀 수 있다.

따라서 현재 몸무게를 2, 기억하고 있던 몸무게를 1로 설정하고 제곱의 차이를 diff라고 했을 때 이 값이 G보다 작으면 현재 몸무게를 증가, G보다 크다면 기억하고 있던 몸무게를 증가, G라면 현재 몸무게를 출력하고 G가 되는 더 큰 현재 몸무게가 있는지 확인하기 위해 현재 몸무게를 증가시켜서 다시 확인한다.

이렇게 확인하려면 현재 몸무게가 끝도없이 증가할 수 있으므로 끝나는 조건을 잡아야 한다. 문제에서 주어지는 범위는 G의 최댓값이므로 여기서 현재 몸무게의 최댓값을 생각해보아야 한다. 먼저 수식으로 나타내기 위해 현재 몸무게를 y, 기억하고 있는 몸무게를 x라고 하면 다음과 같은 수식이 나온다.

$G = y^2 - x^2$

이를 다시 y에 관한 식으로 나타내면 $y^2 = G + x^2$가 된다. 즉 기억하고 있는 몸무게의 제곱이 클 수록 현재 몸무게가 증가한다는 것이고 이 문제에서 기억하고 있는 몸무게는 현재 몸무게보다 작아야 하므로 둘 다 자연수라고 생각하면 x의 최댓값은 y - 1이 된다. 이때 식을 다시 쓴다면 $y^2 = G + (y - 1)^2$이 되고 다시 쓰면 $G = y^2 - (y - 1)^2 = 2y - 1$이 된다.

즉, $G = 2y - 1 \leq 100,000$이므로 이를 다시 쓰면 $2y \leq 100,001$ 즉 현재 몸무게는 자연수로 50000까지 된다는 뜻이다. 따라서 투 포인터로 값을 확인할 때 현재 몸무게가 50000까지 확인하면 된다는 것이다.

이에 따라 투 포인터로 현재 몸무게의 제곱에서 기억하고 있던 몸무게의 차가 G가 되는 모든 현재 몸무게를 찾아서 출력하면 정답이 된다.

소스 코드

fun main(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val G = br.readLine().toInt()
    var before = 1L
    var after = 2L
    var find = false
    while(after <= 50001){
        val diff = after * after - before * before
        if(diff < G){
            after++
        } else if(diff > G){
            before++
        } else {
            find = true
            bw.append("$after")
            bw.newLine()
            after++
        }
    }
    if(!find){
        bw.append("-1")
    }
    bw.flush()
    bw.close()
}