[김태원 알고리즘] 최대 선 연결하기 (DP)

사용 언어: Python3

문제

풀이

내 풀이

N = int(input())
lst = list(map(int, input().split()))

right_idx = [0] * (N+1) # ✅ 오른쪽 번호들의 인덱스 정보
for i, val in enumerate(lst):
    right_idx[val] = i # val이 몇 번 인덱스에 위치해있는지

cnt = [0] * (N+1) # ✅ lst의 각 선을 무조건 연결한다고 가정할 때, 최대로 연결할 수 있는 선의 수
cnt[1] = 1 # 1번(인덱스 아니고 값) 선을 무조건 연결했을 때 선의 수는 무조건 1

for i in range(2, N+1):
    mx = 0
    for j in range(1, i):
        if right_idx[i] > right_idx[j]:
            mx = max(mx, cnt[j])
    cnt[i] = mx + 1

print(max(cnt))

• 성공!

다른 풀이

이 문제는 바로 이전에 풀어본 최대 부분 증가수열 문제와 동일한 문제이다.
선이 교차하지 않으려면, 오른쪽 번호 정보 중 “증가수열”만 골라야하고,
결국 그 부분 증가수열의 길이의 최댓값을 구하는 문제이다.

N = int(input())
lst = list(map(int, input().split()))

dp = [0] * N # ✅ lst[i]를 무조건 선택했을 때 부분 증가수열의 길이
dp[0] = 1 # lst[0]을 무조건 선택 -> 길이는 1

for i in range(1, N):
    mx = 0
    for j in range(i):
        if lst[j] < lst[i]:
            mx = max(mx, dp[j])
    dp[i] = mx + 1

print(max(dp))

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기