[코딩테스트] 백준 - DP문제 오답 모음(SilverⅤ~SilverⅠ)

2025.05.02~ (추가 중)

 

✔️백준 #11722 "가장 긴 감소하는 부분 수열"

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

 

문제 요약

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성
ex) A = {10, 30, 10, 20, 20, 10} → A' = {30, 20, 10} & 길이 3

 

▫️입력:

    ▪️첫째 줄: 수열 A의 크기 N (1 ≤ N ≤ 1,000)

    ▪️둘째 줄: 수열 A를 이루고 있는 Ai (1 ≤ Ai ≤ 1,000)

▫️출력: 수열 A의 가장 긴 감소하는 부분 수열의 길이 출력  

 

나의 정답

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

# DP 배열 초기화
F = [1] * N  # 각 원소는 자기 자신으로 시작 가능하므로 1로 초기화

# DP식 구현
for i in range(N):  	# 현재 위치
    for j in range(i):  # 이전 위치
        if seq[i] < seq[j]:
            F[i] = max(F[i], F[j] + 1)

# 결과 출력
print(max(F))

 

풀이 예시

N = 6, seq = [10, 30, 10, 20, 20, 10]

F: 감소하는 부분 수열의 길이를 저장하는 DP배열

 

▪️i = 0 (A[0] = 10)

   ▫️이전 비교할 항 없음 → 그대로

   ▫️F = [1, 1, 1, 1, 1, 1]

---

▪️i = 1 (A[1] = 30)

   ▫️j = 0 (A[0] = 10) → 30 < 10 ❌

   ▫️F = [1, 1, 1, 1, 1, 1]

---

▪️i = 2 (A[2] = 10)

   ▫️j = 0 (A[0] = 10) → 10 < 10 ❌

   ▫️j = 1 (A[1] = 30) → 10 < 30 ✅ → F[2] = max(1, F[1] + 1) = max(1, 2) = 2

   ▫️F = [1, 1, 2, 1, 1, 1]

---

▪️i = 3 (A[3] = 20)

   ▫️j = 0 (A[0] = 10) → 20 < 10 ❌

   ▫️j = 1 (A[1] = 30) → 20 < 30 ✅ → F[3] = max(1, F[1] + 1) = 2

   ▫️j = 2 (A[2] = 10) → 20 < 10 ❌

   ▫️F = [1, 1, 2, 2, 1, 1]

---

▪️i = 4 (A[4] = 20)

   ▫️j = 0 (A[0] = 10) → 20 < 10 ❌

   ▫️j = 1 (A[1] = 30) → 20 < 30 ✅ → F[4] = max(1, F[1] + 1) = 2

   ▫️j = 2 (A[2] = 10) → 20 < 10 ❌

   ▫️j = 3 (A[3] = 20) → 20 < 20 ❌

   ▫️F = [1, 1, 2, 2, 2, 1]

---

▪️i = 5 (A[5] = 10)

   ▫️j = 0 (A[0] = 10) → 10 < 10 ❌

   ▫️j = 1 (A[1] = 30) → 10 < 30 ✅ → F[5] = max(1, F[1]+1) = 2

   ▫️j = 2 (A[2] = 10) → 10 < 10 ❌

   ▫️j = 3 (A[3] = 20) → 10 < 20 ✅ → F[5] = max(2, F[3]+1) = 3

   ▫️j = 4 (A[4] = 20) → 10 < 20 ✅ → F[5] = max(3, F[4]+1) = 3

   ▫️F = [1, 1, 2, 2, 2, 3]

틀린 이유

DP 배열에 부분 수열의 길이를 저장하는 것까지는 생각했는데, DP식을 제대로 세우지 못함... 

특히, max(F[i], F[j]+1)을 생각 못했음 ㅠ!

---

✔️백준 #15486 "퇴사2"

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

 

문제 요약

 

▫️입력:

    ▪️

▫️출력: 

 

나의 정답

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

# DP 배열 초기화
F = [1] * N  # 각 원소는 자기 자신으로 시작 가능하므로 1로 초기화

# DP식 구현
for i in range(N):  	# 현재 위치
    for j in range(i):  # 이전 위치
        if seq[i] < seq[j]:
            F[i] = max(F[i], F[j] + 1)

# 결과 출력
print(max(F))

 

틀린 이유