[알고리즘 기초] - 401-다이나믹 프로그래밍 1(연습)

양진혁·2022년 11월 29일

백준

목록 보기

19/21

15988_1, 2, 3 더하기 3

⭕풀이:

import sys

input = sys.stdin.readline

dp = [1, 2, 4, 7]
for i in range(int(input())):
    n = int(input())
    for j in range(len(dp), n):
        dp.append((dp[-3] + dp[-2] + dp[-1]) % 1000000009)
    print(dp[n - 1])

⭕풀이설명:

dp[-3] + dp[-2] + dp[-1])

1149_RGB거리

⭕풀이:

n = int(input())
p = []
for i in range(n):
    p.append(list(map(int, input().split())))
for i in range(1, len(p)):
    p[i][0] = min(p[i - 1][1], p[i - 1][2]) + p[i][0]
    p[i][1] = min(p[i - 1][0], p[i - 1][2]) + p[i][1]
    p[i][2] = min(p[i - 1][0], p[i - 1][1]) + p[i][2]
print(min(p[n-1]))

⭕풀이설명:

red의 경우, green의 경우, blue의 경우 중 min

우선, 두 번째 집을 기준으로 시작해 해당 집(= [i])을
빨간 집으로 칠했을 경우, R [i][0]
초록 집으로 칠했을 경우, G [i][1]
파란 집으로 칠했을 경우, B [i][2]
를 모두 계산하는데 그 이전의 값들 중 같은 색을 제외한 값들에서 min을 통해 최솟값을 더해주는 것을 반복하고, 이를 RGB 리스트에서 업데이트하면
해당 집[i]을 세 가지 색[0,1,2]으로 칠한 가격 + 그 이전의 집[i-1]이 해당하는 색을 제외한 [1,2], [0,2], [0,1] 중 최소 가격을 더한 값이
RGB의 [[첫 번째 집의 R,G,B][첫 번째 집 R,G,B + 두 번째 집 R,G,B][..][..]]로 업데이트 될 수 있습니다.
따라서 이 3개의 값 중에서 가장 작은 값을 출력해주면 됩니다.

1309_동물원

⭕풀이:

n = int(input())
dp = [1, 3] + [0] * (n - 1)
for i in range(2, n + 1):
    dp[i] = (dp[i - 2] + dp[i - 1] * 2) % 9901
print(dp[n])

https://hooongs.tistory.com/151
https://my-coding-notes.tistory.com/264

11057_오르막 수

⭕풀이:

n = int(input())
dp = [1] * 10
for i in range(1, n):
    for j in range(1, 10):
        dp[j] += dp[j - 1]

print(sum(dp) % 10007)

⭕풀이설명:

num[i] += num[i-1]

https://animoto1.tistory.com/entry/%EB%B0%B1%EC%A4%80-11057-%EC%98%A4%EB%A5%B4%EB%A7%89-%EC%88%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python

9465_스티커

⭕풀이:

t = int(input())
for i in range(t):
    s = []
    n = int(input())
    for k in range(2):
        s.append(list(map(int, input().split())))
    for j in range(1, n):
        if j == 1:
            s[0][j] += s[1][j - 1]
            s[1][j] += s[0][j - 1]
        else:
            s[0][j] += max(s[1][j - 1], s[1][j - 2])
            s[1][j] += max(s[0][j - 1], s[0][j - 2])
    print(max(s[0][n - 1], s[1][n - 1]))

⭕풀이설명:

https://pacific-ocean.tistory.com/197

2156_포도주 시식

⭕풀이:

⭕풀이설명:

dp[i - 1], dp[i - 3] + w[i - 1] + w[i], dp[i - 2] + w[i]

규칙은 두 가지입니다.

첫 번째로 해당 순서의 포도주를 마시는 경우,
그 전 포도주를 마시는 경우와 안 마시는 경우가 있습니다.
두 번째로 해당 순서의 포도주를 마시지 않는 경우가 있습니다.

w가 포도주의 양을 담은 리스트라고 할 때, 다음과 같이 표로 정리할 수 있습니다.

위의 표에서 경우의 수를 보면,

dp[3]의 경우의 수에서 w1 + w2는 dp[2]와 같습니다.

w1 + w2 = dp[2]

dp[4]의 경우의 수를 보면 w2 + w3은 dp[3]이고,
w1 + w2 + w4 에서 w1 + w2는 dp[2]이고,
w1 + w3 + w4 에서 w1은 dp[1]입니다.

w2 + w3 = dp[3]
w1 + w2 + w4 = dp[2] + w4
w1 + w3 + w4 = dp[1] + w3 + w4

그래서 식을 세워보자면,
dp[4]의 경우의 수는

dp[4-1], dp[4-3] - w[4-1] + w[4], dp[4-2] + w[4] 로

4를 i로 바꿨을 때,

dp[i-1], dp[i-3] + w[i-1], dp[i-2] + w[i]

이 세가지 값 중 가장 큰 값이 구하고자 하는 값이 됩니다.

https://pacific-ocean.tistory.com/152

1932_정수 삼각형

⭕풀이:

test_case = int(input())
arr = []

for _ in range(test_case):
    numbers = list(map(int, input().split()))
    arr.append(numbers)
k = 2
for i in range(1, test_case):
    for j in range(k):
        if j == 0:
            arr[i][j] += arr[i - 1][j]
        elif i == j:
            arr[i][j] += arr[i - 1][j - 1]
        else:
            arr[i][j] = max(arr[i - 1][j - 1], arr[i - 1][j]) + arr[i][j]
    k += 1
print(max(arr[test_case - 1]))

⭕풀이설명:

위의 그림에서 보았을때, 맨 밑의 자리 즉, 4 5 2 6 5 각 자리에 올 수 있는 가장 큰 값을 구하고, 그 값들 중에서 가장 큰 값을 출력해주면 됩니다.

맨 왼쪽 숫자들과 맨 오른쪽 숫자들은 바로 자기 위 숫자를 더하면 됩니다.
나머지 숫자들은 왼쪽 위 숫자와 오른쪽 위 숫자를 비교해 큰 값을 더합니다.

한번 for문을 돌렸을때, 두번째 줄은 10, 15가 됩니다.

두번째 for문에서 세번째 줄은 18, 16, 15가 됩니다.

이렇게 쭉쭉 내려와 마지막 숫자들 중 가장 큰 값을 출력합니다.

11055_가장 큰 증가부분 수열

⭕풀이:

n = int(input())
numbers = list(map(int, input().split()))
dp = [0] * n
dp[0] = numbers[0]
for i in range(1, n):
    arr = []
    for j in range(i - 1, -1, -1):
        if numbers[i] > numbers[j]:
            arr.append(dp[j])
    if not arr:
        dp[i] = numbers[i]
    else:
        dp[i] = numbers[i] + max(arr)
print(max(dp))

⭕풀이설명:

dp = [1, 101, 3, 53, 113, 6, 11, 17, 24, 32]

수열 a = [1, 100, 2, 50, 60, 3, 5, 6, 7, 8]이라고 했을때,
dp에는 각 자리에 올 수있는 가장 큰 값을 넣게 하려고 합니다.
그러면,

dp = [1, 101, 3, 53, 113, 6, 11, 17, 24, 32]

같이 만들 수 있습니다.

dp[i]에 오게될 값은 a[0] ~ a[i - 1]의 값 중 a[i]보다 작은 값의 인덱스를 구한 뒤
그 인덱스에 맞는 dp의 값 중 가장 큰 값을 a[i]에 더하면 됩니다.

예를 들어 dp[4]에 오게 될 값을 구해보면은 다음과 같습니다.
a[0] 부터 a[3]까지 a[4]보다 작은 값의 인덱스는 0(1), 2(2), 3(50) 입니다.
이때, dp0, dp2, dp3중 가장 큰 값은 53이므로

dp[4] = a[4] + dp[3] 즉 dp[4] = 113이 올 수 있습니다.

11722_가장 긴 감소하는 부분 수열

⭕풀이:

n = int(input())
nums = list(map(int, input().split()))
dp = [1 for i in range(n)]
for i in range(n):
    for j in range(i):
        if nums[j] > nums[i]:
            dp[i] = max(dp[i],dp[j]+1)
print(max(dp))

https://pacific-ocean.tistory.com/209

11054_가장 긴 바이토닉 부분 수열

⭕풀이:

n = int(input())
numbers = list(map(int, input().split()))
dpp = [0] * n
dpm = [0] * n
dpb = [0] * n

for i in range(n):
    for j in range(i):
        if numbers[i] > numbers[j] and dpp[i] < dpp[j]:
            dpp[i] = dpp[j]
    dpp[i] += 1
for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
        if numbers[i] > numbers[j] and dpm[i] < dpm[j]:
            dpm[i] = dpm[j]
    dpm[i] += 1
for i in range(n):
    dpb[i] = dpp[i] + dpm[i] - 1
print(max(dpb))

https://pacific-ocean.tistory.com/158

13398_연속합 2

⭕풀이:

import sys

input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))
dp = [[x for x in numbers] for _ in range(2)]

for i in range(1, n):
    dp[0][i] = max(dp[0][i - 1] + numbers[i], dp[0][i])
    dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + numbers[i])

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

⭕풀이설명:

dp[0][i] = max(dp[0][i - 1] + numbers[i], dp[0][i])

dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + numbers[i])

dp를 2중 리스트로 선언해 2가지 dp를 비교하면서 둘 중 큰 값을 찾는 문제입니다.
dp는 다음과 같이 변수선언할 수 있습니다.

dp = [[numbers], [numbers]]

dp[0][i]는 특정 요소값을 제거하지 않은 경우,

dp[1][i]는 특정 요소값을 제거한 경우입니다.

n이 1보다 클 경우 dp를 찾으면 됩니다.

1) 특정 원소를 제거하지 않은 경우

dp[0][i] = max(dp[0][i - 1] + numbers[i], dp[0][i]) 는 아무런 요소값을 제거하지 않고, 일반적인 연속합으로 구하는 경우입니다.

2) 특정 원소를 제거하는 경우

dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + numbers[i]) 는 다음의 두 가지 상황 중 큰 값을 대입하면 됩니다.

i번째 요소값을 제거하는 경우 -> 위에서(dp[0]에서) 구한 i-1 번째 연속 합의 최대값을 그대로 dp[1][i]에 대입합니다.

i번째 이전의 요소값을 이미 제거하여 이전에 구해놓은 dp 값에 현재 i값을 더해주는 경우
-> i번째 이전의 요소값을 제거한 연속합 값 + 현재 i번째 요소값을 더한 값을 dp[1][i]에 대입합니다.

https://ji-gwang.tistory.com/289

2133_타일 채우기

⭕풀이:

n = int(input())
dp = [0] * 31
dp[2] = 3
for i in range(4, 31, 2):
    dp[i] = dp[2] * dp[i - 2]
    for j in range(4, i, 2):
        dp[i] += 2 * dp[i - j]
    dp[i] += 2
print(dp[n])

⭕풀이설명:

우선 직접 n에 수를 대입했을때,
n이 홀수일 경우, 경우의 수는 0인 점을 알 수 있습니다.

n=2 인 경우,
경우의 수는 3 입니다.

n=4 인 경우,
경우의 수는 11입니다.
dp[2] * dp[2] 에
새로운 모양 2개를 더해줍니다.

dp[2] * dp[2] + 2

n=6 인 경우,
경우의 수는 41입니다.
dp[2] dp[4] 에
새로운 모양 4 dp[2] 를 더하고,
새로운 모양 2개를 더해줍나다.

dp[2] dp[4] + 4 dp[2] + 2

n=8 인 경우,
경우의 수는 153입니다.
dp[2] dp[6] 에
새로운 모양 4 dp[4] 를 더하고,
새로운 모양 6 * dp[2] 를 더하고,
새로운 모양 2개를 더해줍니다.

dp[2] dp[6] + 4 dp[4] + 6 * dp[2] + 2

양진혁

타이밀크티는 맛있습니다.

이전 포스트

[알고리즘 기초] - 400-다이나믹 프로그래밍 1

다음 포스트

[알고리즘 기초] - 401-다이나믹 프로그래밍 1(연습)

백준

15988_1, 2, 3 더하기 3

⭕풀이:

⭕풀이설명:

dp[-3] + dp[-2] + dp[-1])

1149_RGB거리

⭕풀이:

⭕풀이설명:

red의 경우, green의 경우, blue의 경우 중 min

1309_동물원

⭕풀이:

11057_오르막 수

⭕풀이:

⭕풀이설명:

num[i] += num[i-1]

9465_스티커

⭕풀이:

⭕풀이설명:

2156_포도주 시식

⭕풀이:

⭕풀이설명:

dp[i - 1], dp[i - 3] + w[i - 1] + w[i], dp[i - 2] + w[i]

1932_정수 삼각형

⭕풀이:

⭕풀이설명:

11055_가장 큰 증가부분 수열

⭕풀이:

⭕풀이설명:

dp = [1, 101, 3, 53, 113, 6, 11, 17, 24, 32]

11722_가장 긴 감소하는 부분 수열

⭕풀이:

11054_가장 긴 바이토닉 부분 수열

⭕풀이:

13398_연속합 2

⭕풀이:

⭕풀이설명:

dp[0][i] = max(dp[0][i - 1] + numbers[i], dp[0][i])

dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + numbers[i])

2133_타일 채우기

⭕풀이:

⭕풀이설명:

dp[2] * dp[2] + 2

dp[2] dp[4] + 4 dp[2] + 2

dp[2] dp[6] + 4 dp[4] + 6 * dp[2] + 2

[알고리즘 기초] - 400-다이나믹 프로그래밍 1

[알고리즘 기초] - 402-다이나믹 프로그래밍 1(도전)

0개의 댓글

**dp[2] * dp[2] + 2**

**dp[2] dp[4] + 4 dp[2] + 2**