✏️ 서론
오늘도 마찬가지로 어제 풀었던 DP 다양한 문제 유형을 접해보는 시간을 가졌다.
백준의 문제가 어렵다고 생각해 코드업에서도 몇 문제 풀었는데
(코드업도 어려워 젠장..)
한번 살펴보자!
✏️ 본론
⚡️ [ 문제 1 ] 개미전사
개미전사문제는 리스트안에서 최대값을 구하는 문제인데,
연속된 값이 아닌 최소한 한 칸이상 떨어진 값들 중에서 최대값을 구하는 문제이다.
초기값인 d[0], d[1]값은 잘 구했는데
점화식을 구현하지 못해 쩔쩔맸었다.
어려운 문제는 아니고 타일링과 비슷한 문제였다.
접근 방식을 뒤에서부터 차근차근 접근해보자.
전체 길이가 i인 사각형이 있다고 가정해보자.
그럼, 길이가 1만큼의 사각형을 잘라내면 남은 길이는 i-1이 남는다.
만약, 사각형의 제일 끝부분이 식량창고로 쓸 수 있다고 가정하면 1만큼 잘라낸 사각형은 사용 할 수 없다.i-1
왜냐하면, 문제에서 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.라는 가정이 있기 때문이다.
그러므로 d[i-1]이 성립된다.
반대로, i-1 사각형의 제일 끝부분이 식량창고로 쓸 수 없다면 k만큼 잘라낸 다음칸은 식량창고로 사용 할 수 있고 i-2번째도 식량창고로 사용 할 수 있다.
왜냐하면, 문제에서 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.라는 가정이 있기 때문이다.
그러므로 d[i-2]에 남은 k만큼의 길이를 더해주면 된다.
따라서, d[i-2] + k[i]가 성립한다.
식량의 최대값을 구하는 문제이기 때문에 max함수를 사용한다.
점화식은 다음과 같다.
a(i) = max(d[i-1], d[i-2] + array[i])
'''
3
'''
n = int(input())
array = list(map(int, input().split()))
d = [0] * 100
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
d[i] = max(d[i-1], d[i-2] + array[i])
print(d[n-1])
👉🏽 5⚡️ [ 문제 2 ] 백준 1912 - 연속합
어떤 리스트가 있을 때 연속된 구간의 최대합을 출력하는 문제이다.
이 문제의 규칙을 찾기가 어려워서 다른사람은 어떻게 풀었는지 참고하던 중 이 분의 설명이 이해하기 쉬웠다.
티스토리 - 네로의 다락방
DP문제의 핵심은 점화식을 어떻게 만드느냐에 따라 갈리는데,
처음에 이해가 되지 않는다면 모든 경우의 수를 구해 규칙을 찾는 편이 수월하다.
하지만 데이터가 많을 수록 불가능하기 때문에 이전에 규칙을 찾아두자.
이 문제의 핵심을 요약해서 설명하자면 다음과 같다.
array[i]의 현재값보다d[i-1] + array[i]가 더 크면d[i] = d[i-1] + array[i]이고,
그렇지 않으면d[i] = array[i]이다.
for i in range(1, n):
if d[i-1] + array[i] > array[i]:
d[i] = d[i-1] + array[i]
else:
d[i] = array[i]d[i] = max(d[i-1] + array[i], array[i])
'''
10
10 -4 3 1 5 6 -35 12 21 -1
10
2 1 -4 3 4 -4 6 5 -5 1
5
-1 -2 -3 -4 -5
'''
import sys
n = int(input())
array = list(map(int, sys.stdin.readline().split()))
d = [0] * n
d[0] = array[0]
for i in range(1, n):
if d[i-1] + array[i] > array[i]:
d[i] = d[i-1] + array[i]
else:
d[i] = array[i]
print(max(d))
👉🏽 33 14 -1⚡️ [ 문제 3 ] 코드업 3704 - 계단 오르기 2
피보나치 수열 변형 문제이다.
직접 공책에 그려가면서 규칙을 찾았는데 경우의 수를 따져보며 찾으면 된다.
d[i] = d[i-1] + d[i-2] + d[i-3]
점화식이 3개까지 있기 때문에 초기값도 3개를 선언해줬다.
for문 범위설정에 주의하자.
'''
5
'''
n = int(input())
d = [0] * 100001
d[1] = 1
d[2] = 2
d[3] = 4
for i in range(4, n+1):
d[i] = (d[i-1] + d[i-2] + d[i-3]) % 1000
print(d[n])
👉🏽 13✏️ 결론
이렇게 동적프로그래밍 단원이 끝이났다. (문제는 아주 많이 남았다.)
한 문제를 풀때마다 오래 붙잡고 있어서 그런지 단계별 풀이에서 진도가 잘 나가지 않는다.
그리고 갈수록 알고리즘의 난이도가 어려워지는것 같다. 😂 😂
단기간에 모든걸 잡으려고 하면 안되겠다는 생각이 들었다.
다른 개념을 배우고 오면 접근을 더 잘 할수있을까?
내일은 최단경로에 대해 배워보자!
