[12892] 생일 선물

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

12892번: 생일 선물

투 포인터 문제다.

 

풀이

입력받은 P와 V를 pair로 생성하여 배열에 담는다. N이 100,000이기에 P를 기준으로 오름차순 정렬한 뒤 탐색을 시작해도 시간초과가 일어나지 않는다.

 

tail과 head가 가리키는 P의 차이가 D보다 작다면, 더 많은 선물을 받을 수 있다는 얘기이므로 선물의 범위를 늘리기 위해 tail을 증가시킨 후 tail이 가리키는 만족도 V를 추가하여 더 큰 값으로 갱신한다.

 

만일 P의 간격이 D이상이라면, 선물을 받을 수 없는 상황이다. head가 가리키는 만족도 V를 뺀 후 head를 증가시켜 선물을 받는 범위를 좁힌다. tail이 N에 도달하면 반복문을 종료한다.

 

정답 코드

	import Foundation
	let nd = readLine()!.split(separator: " ").map{Int($0)!}
	let n = nd[0]
	let d = nd[1]
	var arr = [(p:Int,v:Int)]()
	for _ in 0..<n{
	let info = readLine()!.split(separator: " ").map{Int($0)!}
	arr.append((info[0],info[1]))
	}
	arr.sort(by: {$0.p < $1.p})
	var head = 0
	var tail = 0
	var sum = 0
	var ans = 0
	while tail < n{
	if arr[tail].p-arr[head].p >= d{
	sum -= arr[head].v
	head += 1
	}else if tail < n{
	sum += arr[tail].v
	tail += 1
	ans = max(ans, sum)
	}
	}
	print(ans)

view raw 12892.swift hosted with ❤ by GitHub