https://www.acmicpc.net/problem/12892
12892번: 생일 선물
첫 줄에 친구의 수 N(1 ≤ N ≤ 100,000)과 미안함을 느끼게 되는 최소가격차 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 선물의 가격 P와 만족도 V(0 ≤ P ≤ 1,000,000,000, 0
www.acmicpc.net
투 포인터 문제다.
풀이
입력받은 P와 V를 pair로 생성하여 배열에 담는다. N이 100,000이기에 P를 기준으로 오름차순 정렬한 뒤 탐색을 시작해도 시간초과가 일어나지 않는다.
tail과 head가 가리키는 P의 차이가 D보다 작다면, 더 많은 선물을 받을 수 있다는 얘기이므로 선물의 범위를 늘리기 위해 tail을 증가시킨 후 tail이 가리키는 만족도 V를 추가하여 더 큰 값으로 갱신한다.
만일 P의 간격이 D이상이라면, 선물을 받을 수 없는 상황이다. head가 가리키는 만족도 V를 뺀 후 head를 증가시켜 선물을 받는 범위를 좁힌다. tail이 N에 도달하면 반복문을 종료한다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [6503] 망가진 키보드 (0) | 2023.01.24 |
|---|---|
| [15831] 준표의 조약돌 (0) | 2023.01.23 |
| [6137] 문자열 생성 (0) | 2023.01.20 |
| [22862] 가장 긴 짝수 연속한 부분 수열 (large) (0) | 2023.01.19 |
| [1484] 다이어트 (0) | 2023.01.18 |