파이썬 알고리즘 274번 | [백준 18353번] 병사 배치하기 - DP

274. 병사 배치하기

1) 어떤 전략(알고리즘)으로 해결?

• DP!

2) 코딩 설명

<내 풀이>

import sys
n = int(sys.stdin.readline())
lis = list(map(int, sys.stdin.readline().split()))
dp = [1 for _ in range(n)]

for i in range(1, n) : # dp[i] 를 결정할거야
    for j in range(0, i): 
        # 이전 애들 싹dp[0]~dp[i-1] 을 간볼거야
        if lis[i]<lis[j]: # 이전 애가 나보다 높은 경우
        # 나를 냅두든가 vs 내 이전애 이어받기
            dp[i] = max(dp[i], dp[j]+1) 
print(dp)
print(n-max(dp))

< 내 틀렸던 풀이, 문제점>

출처 : 출처

import sys

n = int(sys.stdin.readline())
lis = list(map(int, sys.stdin.readline().split()))
dp = [0 for _ in range(n+1)]
dp[0] = 0
dp[1] = 1
delete = [0 for _ in range(n+1)]

for i in range(1, n) : 
    if lis[i]<lis[i-1] : # 정상적인 경우
        cand1 = dp[i]+1 # 내 이전 아이에 하나 더 더한 것
        dp[i+1] = cand1

    else : # 내가 더 큰 경우
        # (1) 내 앞에 있는 애 지울 때의 경우
        find = i-1
        j = i-1
        while j>=0:
            if lis[j]>lis[i] :
                find = j
                break
            j-=1

        cand1 = dp[find+1]+1

        # (2) 나 스스로를 지울 때의 경우 - 
        cand2 = dp[i]

        # (1), (2) 중 더 max 값으로 go
        dp[i+1]=max(cand1, cand2)

print(dp)
print(n-max(dp))

(2)

import sys
n = int(sys.stdin.readline())
lis = list(map(int, sys.stdin.readline().split()))
dp = [1 for _ in range(n)]

for i in range(1, n) : # dp[i] 를 결정할거야
    for j in range(0, i): # dp[0]~dp[i-1] 을 간볼거야
        if lis[i]<lis[j]:# 이전 애가 나보다 높은 경우
        # 나를 냅두든가 vs 내 이전애 이어받기
            dp[i] = max(dp[i], dp[j]+1) 
print(dp)
print(n-max(dp))

<반성 점>

• DP 는 늘 원리생각이 어려워!

<배운 점>