2532 - 먹이사슬 / 알고리즘 꿀 팁 !!

요새 가장 긴 증가하는 부분수열에 자신감에 생겼는데,

 

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

2532번: 먹이사슬

 

해당 문제한테 두들겨 맞고, 자신감이 바로 꺾였습니다.

 

분명, 이 문제 카카오 공채 시험 문제였던걸로 생각나고, 풀어 봤던거 같은데, 왤케 틀렸을까요.

---

다행히 아이디어는 떠올랐습니다.

 

시작점을 기준으로 정렬(오름차순)하고, 끝점으로 기준하여 다시 정렬(내림차순) 후, 끝점 기준으로 가장 긴 감소하는 부분 수열, 혹은 뒤집어서 가장 긴 증가하는 부분 수열 만들기 (단 !!! 중복 허용)

 

이렇게 하면 풀립니다.

 

def BS(s, e, v):
    global LB

    if s > e:
        return

    m = (s + e) // 2

    if LIS[m] <= v:
        BS(m + 1, e, v)
    else:
        LB = m
        BS(s, m - 1, v)

N = int(input())
A = []

for _ in range(N):
    id, s, e = map(int, input().split())
    A.append([s, e])

A = sorted(A, key = lambda x: (x[0], -x[1]))[::-1]
LIS = []
LB = 0

for idx in range(len(A)):
    v = A[idx][1]
    if idx > 0 and A[idx][0] == A[idx - 1][0] and A[idx][1] == A[idx - 1][1]:
        continue
    if idx == 0 or LIS[-1] <= v:
        LIS.append(v)
    else:
        BS(0, len(LIS) - 1, v)
        LIS[LB] = v

print(len(LIS))

평소에 가장 긴 증가하는 부분 수열에서

 

시작점, 끝점이 같으면 비교를 생략하고, => 반복문에서 이전 것이 현재 것과 같으면, 그 현재는 로직 out

 

중복을 허용하게 만들어주면 됩니다. => Binary Search의 조건에서 (<를 <=)으로 교체 (여기서 고생 좀 했어용...)

 

(다른 블로그들 뭔 설명을 장황하게 했던데, 다 도움 안됐음, 내가 짱임)

 

---

오늘 글의 핵심 !!!

 

www.dovelet.com

http://www.dovelet.com

 

위의 사이트는 문제가 틀리면, 어떤 예제에서 틀렸는지 보여줍니다 !!!

개 꿀 !!!

문제가 다 있는건 아닌거 같더라고요. 그래도 정보 올림피아드 문제는 좀 있는거 같습니다. 현재까지도 운영하고 있는 사이트 같고요.

 

사랑합니다. 개발자님

 

진짜 왜 맞 틀 ? 에 중독된 분들은 위에 사이트에서 본인의 문제를 제출해보세요.

 

문제는 잘 못이 없습니다.

 

잘 못 된건 당신의 코드니까요 !!!

---

이상 2532 - 먹이사슬 / 알고리즘 꿀 팁 !! 였습니다. ^_^

 

이제 알고리즘 잠시 놓고, Angular 공부를 해야겠다...