[백준 / Python] 15038번 Lounge Lizards
https://www.acmicpc.net/problem/15038
15038번: Lounge Lizards
Monitor lizards are a kind of reptile known mainly for their cold-bloodedness and addiction to computer screens. Due to their love for digital displays, these scaly creatures spend most of their time at home glued to a small television in the lounge. Confl
www.acmicpc.net
문제 분석
난이도
플래티넘5
분류
기하학, LIS(NlogN), 이분탐색, 유클리드 호제법
들어가기 전에
유명한 문제인 가장 "긴 증가하는 부분 수열" 문제의 다이나믹 프로그래밍 O(N^2)의 풀이가 아닌 이분 탐색을 이용한 O(NlogN)의 풀이를 알고 있어야 아이디어를 떠올리기 쉬운 문제
문제
TV와 도마뱀들이 있다. 도마뱀들은 TV를 보고 싶어한다. 도마뱀들에게는 키(높이)값이 존재한다. 키 작은 도마뱀은 자신이 TV를 보는 경로에 자신보다 더 큰 도마뱀이 있다면 TV가 보이지 않는다. 따라서 적절하게 도마뱀들을 제거해서 가장 많은 도마뱀들이 TV를 볼 수 있도록 해보자.
입력
첫 줄에 TV의 좌표(x,y)가 주어진다.
다음 줄에 도마뱀의 수가 주어지고 그 수만큼 도마뱀의 좌표와 키 (x,y,h) 값이 주어진다.
출력
적절히 도마뱀을 제거해서 얻을 수 있는 최대의 TV를 볼 수 있는 도마뱀 수를 출력해라.
문제 풀이
풀이
문제에 대한 이해는 어렵지 않은 편이라 생각한다.
일단 예제 입력을 토대로 한번 설명을 해 보겠다.
50 50
3
60 55 1
70 60 1
40 45 1이와 같은 입력이 들어온 경우 그래프 상으로 이렇게 표현 가능하다.
빨간색 점에 있는 도마뱀 때문에 보라색 점에 있는 도마뱀은 TV를 볼 수 없다. TV까지 같은 직선에 존재하며 동시에 높이가 같기 때문에 가려서 볼 수 없게 된다.
그렇다면 같은 직선상에 존재하는 도마뱀들끼리 모아서 가장 긴 증가하는 부분 수열(이하 LIS)를 구해주면 되는 것이다.
같은 직선상에 존재함을 구하기 위해 사용한 방법은 기울기를 구한 것이다. 단 이때 실제로 소수로 나타나게 되면 소수의 정밀성에 문제로 인해 문제를 틀릴 수 있으므로 분수로 구해서 풀어줄 수 있다. 예를 들어 0.5라면 (분자,분모)로 표현해 (1,2) 이런 식으로 표현해 줄 수 있을 것이다. 따라서 이렇게 기약분수를 구하기 위해서 적절한 라이브러리나 유클리드 호제법을 이용해 줄 수 있다.
이제 같은 직선에 놓인 도마뱀들을 알 수 있다. 이제 이 도마뱀들과 TV까지의 거리순으로 정렬하여 ( 입력이 가까운 순으로 주어지지 않기 때문에) 높이들에 대해 LIS를 구해주면 된다.
LIS를 통해 얻은 배열의 크기들의 합이 곧 답이 된다.
소스코드
from sys import stdin
from bisect import bisect_left
from collections import defaultdict
from math import gcd
input=stdin.readline
def gettilt(x1,y1,x2,y2):
top=y2-y1
bot=x2-x1
if top==0 and bot==0:
return (0,0)
GCD=gcd(top,bot)
return (top//GCD,bot//GCD)
def getdist(x1,y1,x2,y2):
return ((x2-x1)**2+(y2-y1)**2)**0.5
def getlis(arr):
lis=[arr[0][1]]
for i in range(len(arr)):
if lis[-1]<arr[i][1]:
lis.append(arr[i][1])
else:
idx=bisect_left(lis,arr[i][1])
lis[idx]=arr[i][1]
return len(lis)
ti,tj=map(int,input().split())
n=int(input())
dd=defaultdict(list)
for i in range(n):
xi,yi,hi=map(int,input().split())
dd[gettilt(ti,tj,xi,yi)].append((getdist(ti,tj,xi,yi),hi))
ans=0
for i in dd:
dd[i].sort()
ans+=getlis(dd[i])
print(ans)후기