[백준 / Python] 15038번 Lounge Lizards

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

15038번: Lounge Lizards

문제 분석

난이도

플래티넘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)

후기

LIS(nlogn) 자체의 난이도가 G2이다 보니 이 문제의 난이도도 높게 붙은 것 같다.

태그를 검색해서 풀어서 엄청 쉬워지는 유형의 문제이다. 태그를 몰랐다면 한참 해맸을 것 같다.