2021 하계 모각코 6주차 목표와 회고

08 Aug 2021

Reading time ~1 minute

6주차 (08월 08일)

목표

알고리즘 < 다이나믹 프로그래밍 > 문제풀기 (백준 2156번, 백준 11053번, 백준 11054번)

회고

알고리즘 < 다이나믹 프로그래밍 > 문제 : 백준 2156번(“포도주 시식”) -> 난이도 : 실버1

해결 방법 : n번째 잔까지 최대로 마실 수 있는 포도주 양의 경우는 우선 n번째 잔을 마시는 경우와 마시지 않는 경우가 있다. n번째 잔을 마신다고 가정하면 n-1번째 잔을 마시는 경우와 마시지 않는 경우를 생각할 수 있다. n-1번째 잔을 마신다고 가정하면 3잔 연속으로 마시지 못하기 때문에 n-2번째 잔은 마시지 못하고 n-3번째 잔을 마신다고 생각할 수 있다. n-1번째 잔을 마시지 않는다고 가정하면 n-2번째 잔을 마신다고 생각할 수 있다. 위의 경우를 모두 따져서 그중 최대인 값을 dp에 저장한다.

코드일부

for i in range(1, n+1):
    arr[i] = int(input())
    if i == 1:
        dp[i] = arr[i]
    elif i == 2:
        dp[i] = dp[i-1] + arr[i]
    else:
        dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i], dp[i-1])

print(dp[n])

알고리즘 < 다이나믹 프로그래밍 > 문제 : 백준 11053번(“가장 긴 증가하는 부분 수열”) -> 난이도 : 실버2

해결 방법 : dp의 n번째 index에는 수열의 n번째 index보다 전에 있는 수들 중에서 작은 숫자의 수를 저장한다.

코드일부

A = list(map(int, sys.stdin.readline().split()))
for i in range(1, N):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

알고리즘 < 다이나믹 프로그래밍 > 문제 : 백준 11054번(“가장 긴 바이토닉 부분 수열”) -> 난이도 : 골드3

풀다가 시간이 부족해서 아직 해결하지 못했다. 모각코는 끝났지만 개인적으로 알고리즘 공부할 때 이 문제부터 풀어봐야겠다.

2021 하계 모각코