[백준/Kotlin] 다이어트(1484)

문제

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

 

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. 성원이는 엔토피아가 선물해준 저울 위에 올라갔다. “안돼!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! G 킬로그램이나 더 쪘어ㅜㅠ”라고 성원이가 말했다. 여기서 말하는 G킬로그램은 성원이의 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다.

성원이의 현재 몸무게로 가능한 것을 모두 출력하는 프로그램을 작성하시오.

 

[ 입력 ]

첫째 줄에 G가 주어진다. G는 100,000보다 작거나 같은 자연수이다.

 

[ 출력 ]

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

 

---

풀이

- G = (현재 몸무게)^2 - (기억하는 몸무게)^2 = (현재 + 기억)(현재-기억) 임을 이용

- 현재 + 기억 <= G, 현재-기억 <= G이기 때문에 현재+기억을 1부터 G까지로 두고 각 경우마다 체크해본다

// 백준 - 다이어트(1484)
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max
import kotlin.math.min

fun main() {
  val br = BufferedReader(InputStreamReader(System.`in`))
  val G = br.readLine().toInt()

  val answer = StringBuilder()

  // 현재 몸무게: cur / 기억하는 몸무게: pre
  // G = cur^2 - pre^2 = (cur + pre)(cur - pre)
  // cur + pre <= G && cur - pre <= G

  for(i: Int in 1..G) { // 현재 몸무게 + 기억하는 몸무게 = cur + pre
    // G = (cur + pre)(cur - pre) 이므로 G를 (cur + pre)로 나누면 나누어떨어져야 함
    if(G % i != 0) continue

    // cur, pre 값 찾기
    for(j: Int in 1..i/2) {
      val cur = max(j, i-j) // 현재 몸무게
      val pre = min(j, i-j) // 기억하는 몸무게

      var g = (cur + pre) * (cur - pre)
      if(g == G) {
        answer.append(cur).append("\n")
      }
    }
  }

  // 가능한 몸무게가 없을 경우
  if(answer.length == 0) {
    answer.append("-1")
  }

  print(answer)
}