https://www.acmicpc.net/problem/10025
10025번: 게으른 백곰
첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다.
www.acmicpc.net
투 포인터, 슬라이딩 윈도우로 접근한 문제다.
풀이
투 포인터를 사용하여 곰이 얼음에 닿을 수 있는 최대거리 (2*k+1) 범위의 얼음합을 좌표값 0부터 1000,000까지 탐색을 하면 된다. 단 k의 크기가 500,000을 넘는다면 모든 좌표에 있는 얼음을 가져올 수 있으므로, 입력을 받으면서 얼음의 최댓값을 미리 계산하여 출력하면 된다.
정답 코드
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 | |
| let nk = readLine()!.split(separator: " ").map{Int($0)!} | |
| let n = nk[0] | |
| let k = nk[1] | |
| var ans = 0 | |
| var myMax = 0 | |
| var head = 0 | |
| var tail = 2*k | |
| var sum = 0 | |
| var map = Array(repeating: 0, count: 1000001) | |
| for _ in 0..<n{ | |
| let info = readLine()!.split(separator: " ").map{Int($0)!} | |
| let g = info[0] | |
| let x = info[1] | |
| map[x] = g | |
| if x <= 2*k{ sum += map[x] } | |
| myMax += g | |
| } | |
| ans = sum | |
| while tail < 1000000{ | |
| tail += 1 | |
| sum += map[tail] | |
| sum -= map[head] | |
| head += 1 | |
| ans = max(ans, sum) | |
| } | |
| if k >= 500000{ | |
| print(myMax) | |
| }else{ | |
| print(ans) | |
| } |
'Problem Solving > BOJ' 카테고리의 다른 글
| [15565] 귀여운 라이언 (0) | 2023.01.15 |
|---|---|
| [1337] 올바른 배열 (0) | 2023.01.14 |
| [14246] K보다 큰 구간 (0) | 2023.01.12 |
| [2018] 수들의 합 5 (0) | 2023.01.11 |
| [1504] 특정한 최단 경로 (0) | 2023.01.04 |