[WEEK04] DAY31

DAY31

2021.12.01 WED

오늘은 냅색문제 코드를 2차원배열로 수정하면서 중복오류를 잡았고,
C언어 주차가 어떻게 진행될지 대충 파악을 했고
연결리스트가 어떤 자료구조인지 공부했다.

어제 궁금했던 슬랙봇 시간 자동설정은 터미널에서 crontab 이라는 것을 사용한다고 한다.

DP문제를 풀려면 가장 먼저
DP(N)이 뭘 나타낼지 먼저 정한다
그것과 관련된 점화식을 만들어본다

2579 계단오르기

이 문제에서 DP[N]은 'N번째 계단까지 밟았을 때 최대 점수' 를 나타낸다.

그리고 문제에 나온 조건대로 점화식을 세워보면

DP[N] = max( step[N] + step[N-1] + DP[N-3],
........................ step[N] + DP[N-2])

이런식으로 나타내게 된다.

점화식을 먼저 구하는 연습을 많이 해야 한다.

코드

import sys
n = int(sys.stdin.readline())
stairs = [int(sys.stdin.readline()) for _ in range(n)]
dp = [[0 for _ in range(2)] for _ in range(n)]
# dp[n] = n번째 계단까지 밟았을 때 최대 점수

if n == 1:
    print(stairs[0])
else:
    dp[0][0] = stairs[0]
    dp[1][0], dp[1][1] = stairs[1], stairs[1] + stairs[0]

    for i in range(2, n): # n번째 = i
        dp[i][0] = max(dp[i - 2][0], dp[i - 2][1]) + stairs[i] # 규칙2
        dp[i][1] = dp[i - 1][0] + stairs[i] # 규칙1

    print(max(dp[n - 1][0], dp[n - 1][1])) 

.
.
마찬가지로 이 문제에서도 말하고 있는 규칙을 발견해 점화식을 세워준다.

2156 포도주 시식

코드

n = int(input())
wine_list = [int(input()) for x in range(n)]

dp = [0]
dp.append(wine_list[0])
if(n > 1):
    dp.append(wine_list[0] + wine_list[1])
print(wine_list)
print(dp)

# 연속 3잔을 마시지 않아야 하므로
# 1 : 이번 포도주를 먹고 이전 포도주를 먹지 않은 경우
# 2 : 이번 포도주를 먹고 이전 포도주도 먹은 경우
# 3 : 이번 포도주를 먹지 않아야 하는 경우
# 위 세가지 경우를 고려하여 max

for i in range(3, n + 1):
    # wine_list는 0부터 시작하므로 i - 1로 해준다.
    case_1 = wine_list[i - 1] + dp[i - 2]
    case_2 = wine_list[i - 1] + wine_list[i - 2] + dp[i - 3]
    case_3 = dp[i - 1]
    max_value = max(case_1, case_2, case_3)
    
    dp.append(max_value)
    
print(dp[n])

어떤 문제는 문제를 읽어봐도 아이디어가 떠오르지 않는다
더 연습하고 싶은데 시간이 없다
시간을 쪼개고 더 내서 하고 있지만 이것만으론 부족하다.

어떻게 시간을 분배하고 더 내면 될까?