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

 

1484번: 다이어트

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다.

www.acmicpc.net

투포인터 문제다.

 

풀이

두 제곱수간의 차가 G를 만족하는 쌍을 찾아내면 된다. G의 값이 최대 100,000이므로 제곱수를 담은 크기 100,000의 배열을 생성한 후, head와 tail인덱스를 생성하여 인덱스 간 차이를 계산, G보다 작다면 tail을 증가, G이상이라면 head를 증가시켜 차이를 조절하며 탐색한다. 둘의 차가 G라면 tail의 값을 정답으로 출력하면 된다. 그림으로 보면 더 이해하기 쉽다. 정답이 없다면 -1을 출력하는 것도 까먹지 말자.

정답 코드

import Foundation
var arr = Array(repeating: 0, count: 100001)
for i in 0..<100001{ arr[i] = i*i }
let g = Int(readLine()!)!
var head = 1
var tail = 2
var ans = [Int]()
while tail < 100001{
let gap = arr[tail] - arr[head]
if gap > g{
head += 1
}else{
tail += 1
}
if gap == g{
ans.append(tail-1)
}
}
if ans.isEmpty{
print(-1)
}else{
for ans in ans{ print(ans) }
}
view raw 1484.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[6137] 문자열 생성  (0) 2023.01.20
[22862] 가장 긴 짝수 연속한 부분 수열 (large)  (0) 2023.01.19
[2118] 두 개의 탑  (0) 2023.01.17
[1652] 누울 자리를 찾아라  (0) 2023.01.16
[15565] 귀여운 라이언  (0) 2023.01.15

+ Recent posts