[python] 동적계획법(Dynamic Programing)_백준 문제풀이

개념 참고 - https://velog.io/@lhj99apr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Dynamic-Programming%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95

백준 9461 - 파도반 수열

문제 - [https://www.acmicpc.net/problem/9461]
수열의 패턴을 잘 살펴보고, 패턴을 코드로 구현하면 된다.

N = int(input())

def get_length(n):
    if dp[n]:
        return dp[n]
    else:
        if n < 3:
            dp[n] = 1
        else:
            dp[n] = get_length(n-2) + get_length(n-3)
        return dp[n]


for i in range(N):
    n = int(input())
    dp = [False]*n
    print(get_length(n-1))

백준 1149번 - RGB거리

문제 링크 - https://www.acmicpc.net/problem/1149
이 문제는 dp로 푼다는 생각을 못했던 문제다. 여기서 다시 동적프로그래밍으로 풀 수 있는 문제의 조건을 살펴보면, 작은 해가 큰 해에 영향을 끼치는 것, 그 값을 구하기 위해 이전의 값이 반복적으로 사용된다는 점을 확인할 수 있고 DP로 구현할 수 있다.

N = int(input())
cost = []
for i in range(N):
    cost.append(list(map(int, input().split(' '))))

for i in range(1, N):
    cost[i][0] = min(cost[i-1][1], cost[i-1][2]) + cost[i][0]
    cost[i][1] = min(cost[i-1][0], cost[i-1][2]) + cost[i][1]
    cost[i][2] = min(cost[i-1][0], cost[i-1][1]) + cost[i][2]

print(min(cost[-1]))

백준 1932번 - 정수 삼각형

문제 링크 - https://www.acmicpc.net/problem/1932
이 문제는 앞서 풀었던 문제와 유사하지만, 매번 배열의 크기가 달라진다는 차이점이 있다.

n = int(input())
nums = []
for i in range(n):
    nums.append(list(map(int, input().split(' '))))

for i in range(1, n):
    nums[i][0] = nums[i-1][0] + nums[i][0]
    for j in range(1, len(nums[i])-1):
        nums[i][j] = max(nums[i-1][j-1], nums[i-1][j]) +  nums[i][j]
    nums[i][-1] = nums[i-1][-1] + nums[i][-1]

print(max(nums[-1]))

백준 12865번 - 평범한 배낭

문제 링크 - https://www.acmicpc.net/problem/12865