반응형
SMALL
프로그래머스 요격 시스템
-
프로그래머스 요격 시스템 (LV 2)알고리즘 2023. 7. 9. 10:29
이번 문제는 A나라가 B 나라에 미사일 공격을 할 때, B가 A의 공격을 막아낼 수 있는 최소의 미사일 개수를 구하는 문제입니다. A에서 발사된 미사일은 (s,e) 형태로 주어지고 지상과 평행한 직선으로 s~e 사이를 개구간으로 이동합니다. B의 미사일은 x 지점에서 지상과 수직으로 날아가 x좌표에 걸쳐 있는 모든 A의 미사일을 격추시킬 수 있습니다. targets, s와 e 입력의 범위가 큰 것을 확인했고 최대한 반복문을 자제해야겠다는 생각이 들었습니다. 처음 이 문제를 확인했을 때 관련된 문제를 풀어본 경험이 없어 어떻게 풀어야할지 생각이 떠오르지 않았습니다. 우선, 알고리즘적으로 어떤 미사일을 먼저 격추시키는 것이 최소한의 미사일을 사용할 것인지 생각했습니다. 시도 1. e-s 크기가 작은 미사일에..