2550 - 전구

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

2550번: 전구

 

않이...

 

같은 알고리즘을 사용하는 문제인

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

2568번: 전깃줄 - 2

얘는 플레 5 문제이고

 

왜 지금 풀이하는 문제는 골드 3인지 모르겠는데, 둘이 같은 문제입니다.

---

lower_bound로 LIS 구현하여, 그 값들을 역추적하여 구하는 문제입니다.

 

아래의 필기를 이해하시면 됩니다. (거의 방탈출 수준 ㅋㅋㅋ)

아마 문제를 푸신 분은 이해가 되실겁니다.

 

생각해보니 문제 푼 사람이 이 글을 보진 않겠네요.

 

def bs(s, e, t):
    global lower

    if s > e:
        return 

    m = (s + e) // 2

    if LIS[m] > t:
        lower = m
        bs(s , m - 1, t)
    else:
        bs(m + 1, e, t)


N = int(input())
L_ARR = list(map(int, input().split()))
R_ARR = list(map(int, input().split()))

# 1
O_ARR = [0 for n in range(N + 1)]
for i, v in enumerate(R_ARR):
    O_ARR[v] = i + 1

# 2
LIS = []
TRA = []
lower = 0

for l in L_ARR:
    o = O_ARR[l]
    if len(LIS) == 0 or LIS[-1] < o:
        TRA.append(len(LIS))
        LIS.append(o)
    else:
        bs(0, len(LIS) - 1, o)
        LIS[lower] = o
        TRA.append(lower)

# 3
res = []
chk = max(TRA)
for v in TRA[::-1]:
    N -= 1
    if chk == v:
        res.append(L_ARR[N])
        chk -= 1

# 4
print(len(res))
print(' '.join(map(str, sorted(res))))

---

이상 2550 - 전구 였습니다 ^_^

 

추신

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

13711번: LCS 4

이 문제도 똑같은 문제 같은데, 경험치 먹으러 가봅시다. 다음 문제는 이 녀석이다 !