백준(BOJ) 14269 전설의 쌍검 용사(Python)

문제 내용.

 

그리디 문제.

오른손에 들어야 하는 검의 길이는 고정이기 때문에, set에 모든 A를 저장해 중복을 제거한 뒤 오름차순 정렬해 저장했다.

이 검들은 왼손에는 사용해도 되고 하지 않아도 되지만, 반드시 챙겨가야하는 검들이다.

왼손에 들어야 하는 검의 길이는 [B,C] 형태의 구간을 띄기 때문에, 모든 적의 [A, B, C]를 B 기준으로 오름차순 정렬한 뒤 C 기준으로 내림차순 정렬했다.

이렇게 정렬한 이유는, C가 같은 모든 적에 대해서 그 중 가장 B가 큰 적의 [B, C] 구간에 현재 왼손에 들 검이 존재한다면 C가 같은 모든 적에 대해 왼손에 드는 검을 만족시킬 수 있기 때문이다.

그 다음에는 위 set에 저장해둔, 반드시 챙겨가야하는 검들을 오름차순으로 확인하며 현재 보고 있는 검이 현재 구간에 맞는 검인지를 확인한다.

만약 현재 보고 있는 검이 현재 구간에 맞지 않는 경우에는 다음 검으로 넘어가며 검을 체크하는데, 만약 현재 범위에 맞는 검이 존재하지 않는 경우 길이가 현재 구간의 끝값인 검을 새롭게 추가해 현재 검으로 설정한다.

위와 같은 과정을 반복하며 set에 있는 검의 개수와 새롭게 추가한 검의 개수의 합을 출력하면 된다.

 

그러나 이때 한 가지 신경써야할 부분은, 현재 보고 있는 검이 현재 적의 오른손에 들어야하면서 왼손에도 들어야하는 경우이다.

예를 들면 A, B, C가 1 1 1 또는 1 1 2인 경우가 있을 것이다.

위의 두 경우 오른손에 1짜리 검을 들게 되면 왼손에는 들 검이 없게 되므로 새로운 검을 하나 더 들어야한다.

이 점을 고려해 만약 현재 보고 있는 검이 현재 적의 A와 길이가 같다면, 바로 직전 검의 길이를 확인했다.

직전 검의 길이가 현재 적의 구간에 들어있다면 넘기고, 그렇지 않다면 현재 적의 C에 해당하는 검을 드는 것으로 변경했다.

위와 같은 경우가 발생했을 때에는 구간 내에 적어도 2개 이상의 검이 존재하기만 하면 되고, 현재 보고 있는 검이 구간을 만족하는 검 중 가장 큰 검이므로 바로 직전에 확인한 검만 다시 체크해주면 되는 것이다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
n=int(input())
s=set()
L=[]
for i in range(n):
    a,b,c=map(int,input().split())
    s.add(a)
    L.append([a,b,c])
s=list(s)
s.sort()
S=[]
L.sort(key=lambda x:(x[2],-x[1]))
p=0
S.append(0)
ans=0
x=0
while x<n:
    if L[x][1]<=S[-1]<=L[x][2]:
        if S[-1]==L[x][0]:
            if L[x][1]<=S[-2]<=L[x][2]:
                pass
            else:
                S.append(L[x][2])
                ans+=1
        x+=1
    else:
        while p<len(s):
            if s[p]<=L[x][2]:
                S.append(s[p])
                p+=1
            else:
                break
        if L[x][1]<=S[-1]<=L[x][2]:
            pass
        else:
            S.append(L[x][2])
            ans+=1
print(len(s)+ans)

여름에 풀다가 실패한 문제를 이번에 풀었다.

도합 22번 정도 틀린 것 같다.