240408 - DP풀이 모음

[robert-min]

1로 만들기 링크

• 1로 만들려고 할 때, 연산을 사용하는 횟수의 최솟값 문제
• 실행 시간이 매우 짧기 때문에 완전 탐색으로는 어려움
• dp에 저장을 어떤 수로 할 것인지 고민?
  • 처음에 연산을 사용하는 횟수를 생각 -> 이렇게 할 경우 이전에 연산된 값에 따라 저장해야하기 때문에 3차원 배열이 필요하거나 풀이 자체가 어려움
  • dp에 저장하는 값을 i 숫자를 만드는데 필요한 연산의 수로 생각
  • dp[i] = dp[i-1], i % 2 == 0 -> dp[i//2] + 1, i % 3 == 0 -> dp[i//3] 중 최솟값

"""
Return : 1을 만들려고 할 때, 연산을 사용하는 횟수의 최솟값
- x % 3 == 0 -> x // 3
- x % 2 == 0 -> x // 2
- x -= 1

- 연산 횟수
1번 사용
N // 3, N // 2, N -= 1 -> 3경우
2번 사용
- 위의 경우에 * 3

- i 숫자를 만드는데 필요한 연산 수
- i = 2
- i-1 -> + 1
dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 
dp[i] = dp[i-1], i % 2 == 0 -> dp[i//2] + 1, i % 3 == 0 -> dp[i//3] 중 최솟값

"""
import sys
N = int(input())

if N == 1:
    print(0)
elif N < 4:
    print(1)
else:
    dp = [sys.maxsize] * (N+1)

    dp[2] = 1
    dp[3] = 1
    for i in range(4, N+1):
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i//2] + 1)
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i//3] + 1)
        dp[i] = min(dp[i], dp[i-1]+1)
    print(dp[-1])

[robert-min]

1, 2, 3 더하기 링크

• i를 나타내는 방법의 수 고민
• 작은 수 부터 나타내는 방법 확인
  • dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

"""
Return : n을 1, 2, 3의 합으로 나타내는 방법의 수

- i를 나타내는 방법의 수
- 1 : 1
- 2 : 1+1, 2
- 3 : 1+2, 1+1+1,  2+1. 3
- 4 : 1+1+2, 2+2, 1+2+1, 1+1+1+1, 2+1, 3+1, 1+3

- dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
"""
import sys
input = sys.stdin.readline

dp = [0] * 11
dp[1] = 1
dp[2] = 2
dp[3] = 4
for _ in range(int(input())):
    case = int(input())
    if not dp[case]:
        for i in range(4, case+1):
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    print(dp[case])

[robert-min]

계단 오르기 링크

• i번째 계단을 밟았을 때 최대 점수 저장
• i 번째 계단을 밟는 다는 것은 i-1, i-2 계단을 밟는 두가지 경우
• i-1 계단은 i-2계단은 못밟고 i-3 계단을 밟아야 함
  • score[i-1] + score[i] + dp[i-3]
• i-2 계단을 밟는 것은 i-2계단을 밟을 때의 값
  • score[i] + dp[i-2]
• max(dp[i-2], dp[i-3] + stair[i-1]) + stair[i]

"""
Return : 마지막 계단을 밟았을 때, 얻을 수 있는 총 점수의 최댓값

- dp[i]는 i 번째 계단을 밟았을 때 총 점수 최대값을 저장
- i 번째 계단을 밟는다는 것은 i-1 or i-2 계단을 밟았음
- i-1 계단에서 올라오는 경우
    - score[i-1] + score[i] + dp[i-3]
    - dp[i-2] 는 못올라가기 때문
- i-2 계단에서 올라오는 경우
    - score[i] + dp[i-2]
"""
import sys
input = sys.stdin.readline

N = int(input())

stair = [0] + [int(input()) for i in range(1, N + 1)]

if N < 2:
    print(stair[N])
else:
    dp = [0] * (N+1)
    dp[1] = stair[1]
    dp[2] = dp[1] + stair[2]
    for i in range(3, N+1):
        dp[i] = max(dp[i-2], dp[i-3] + stair[i-1]) + stair[i]
    print(dp[i])

[robert-min]

RGB거리 링크

"""
Return : 모든 집을 칠하는 비용의 최솟값
- 빨강, 초록, 파랑 비용

1번집 빨강
2번집 파랑 or 초록
3번집 초록 or 파랑
마지막 집을 칠하는 경우의 수 [N][0], ...
마지막 색이 빨강이면 그 전 파랑-초록 or 초록-파랑 비용의 합
누적된 값

"""
import sys
input = sys.stdin.readline

N = int(input())
rgb = []
for i in range(N):
    rgb.append(list(map(int, input().split())))
# print(rgb)

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