[DP] 11053번, 2579번, 2156번

1. 가장 긴 증가하는 부분 수열

링크 - 가장 긴 증가하는 부분 수열

아이디어

s=[10 20 10 30 20 50] 이 있을 때,
bottom-up방식으로 생각하여 풀이를 해보면, 0번째일 때는 무조건 자신을 포함해야 한다. ->lis[0]=1

1번째일 때는(20) 0번째 값이(10) 자신보다 작기 때문에 lis[1]=lis[0]+1을 해준다.

2번째일 때는 (10) 0번째 값은 자신이랑 같고, 1번째 값은 자신보다 크기 때문에 lis[i]=1을 해준다.

.
.
.
i번째에 LIS를 구하려면 0번~i-1번째까지 자신보다 작은 수가 있는 지 확인하고, 가장 큰 LIS값을 가진 값을 가져와서 +1을 해주어야 한다.

코드

n = int(input())

s= list(map(int,input().split()))

lis=[0]*n

lis[0]=1
for i in range(1,n):
   for j in range(i):
       if s[j]<s[i] and lis[j]>lis[i]:
           lis[i] = lis[j]
   lis[i]+=1

print(max(lis))   

2. 계단오르기

링크 - 계단오르기

아이디어

bottom-up방식으로 풀이
1번째에서는 무조건 올라야 한다.
2번째는 1번째, 2번째를 올라야 한다.
3번째는 세 번 연속으로 계단을 오를 수 없기 때문에 경우의 수가 2가지가 있다.

1. 1번과 3번을 오름
2. 2번과 3번을 오름

(dp[2]를 가져오는 경우가 없는 이유 - 조건 3의 마지막 계단은 무조건 올라야 한다는 조건이 있기 때문이다.)

4번째는 (1,3,4) (1,2,4)의 경우가 생기게 된다.
.
.
.
dp[i] = max(dp[i-3]+s[i-1],dp[i-2])+s[i]의 점화식을 얻을 수 있게 된다.

코드

n = int(input())
s=[]
for i in range(n):
    s.append(int(input()))

dp=[0]*n

if n>=3:
    dp[0] = s[0]
    dp[1] = s[0]+s[1]
    dp[2] = max(s[1]+s[2],s[0]+s[2])
    if n>3:
        for i in range(3,n):
            dp[i] = max(dp[i-3]+s[i-1],dp[i-2])+s[i]
    print(dp[-1])
    
else:
    print(sum(s))

3. 포도주 시식

링크 - 포도주 시식

아이디어

계단오르기에서 조건3이 빠진 문제이다.
그러면 경우의 수에서 하나가 더 추가가 된다.

1. dp[i-3]+s[i-1]+s[i]
2. dp[i-2]+s[i]
3. dp[i-1] (i번째는 안마심)

코드

n = int(input())
s=[]
for i in range(n):
    s.append(int(input()))
    
dp=[0]*n

if n>=3:
    dp[0] = s[0]
    dp[1] = s[0]+s[1]
    dp[2] = max(s[1]+s[2],s[0]+s[2],dp[1])

    if n>3:
        for i in range(3,n):
            dp[i] = max(dp[i-3]+s[i-1]+s[i],dp[i-2]+s[i],dp[i-1])
    print(dp[-1])
    
else:
    print(sum(s))