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을 출력하는 것도 까먹지 말자.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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) } | |
| } |
'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 |