다이나믹 프로그래밍 낙서장
~
헤..헤헤.. 다이나믹 프로그래밍.. 어..어렵다..헤헤..
백준 1463번: 1로 만들기(Silver III)
'''
백준 1463번: 1로 만들기(Silver III)
https://www.acmicpc.net/problem/1463
다이나믹 프로그래밍
'''
N = int(input())
dp = [0] * 1000001
dp[1] = 0
for i in range(2, N+1):
dp[i] = dp[i-1] + 1 # 3. 메모이제이션
# 2 or 3으로 나누어 떨어지는 경우, 메모이제이션된 부분과 연산횟수를 비교해 최솟값을 저장한다.
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)
print(dp[N])
백준 24416번: 알고리즘 수업 - 피보나치 수 1(Bronze I)
'''
백준 24416번: 알고리즘 수업 - 피보나치 수 1(Bronze I)
https://www.acmicpc.net/problem/24416
수학, 다이나믹 프로그래밍
재귀의 code 1 실행 부분은 그 재귀의 결과와 같다.
DP의 code 2 실행 부분은 N이 2 이하일 때 1이고, 2 초과일 때 N-2이다.
'''
dp = [0] * 41
dp[1] = 1
dp[2] = 1
def fib(n):
if n <= 2:
return 1
for i in range(3, n+1):
dp[i] = dp[i-2] + dp[i-1]
return dp[n]
N = int(input())
codeone = fib(N)
codetwo = 1 if N <= 2 else N-2
print(codeone, codetwo)
백준 1912번: 연속합(Silver II)
'''
백준 1912번: 연속합(Silver II)
https://www.acmicpc.net/problem/1912
다이나믹 프로그래밍
앞에서부터 연속합을 구하다가 합보다 작은 수가 나오면 이후부터 다시 연속합을 구함.
최대값은 연속합을 구하면서 계속 갱신
'''
# 최초 성공 코드(DP보다는 Greedy에 가까운?듯한 코드(156ms)
'''
N = int(input())
numbers = list(map(int, input().split()))
maxnum = -1001
lst = []
for number in numbers:
if maxnum == -1001:
if number < 0: # 반례(-10, 50, 100, 100, 100) -> 첫 값이 음수인 경우 배제
if len(lst) == 0 or max(lst) < number:
lst.append(number)
continue
maxnum = number
else:
if number < 0: # number가 음수인 경우
lst.append(maxnum) # 일단 연속합의 최대값을 저장
if abs(maxnum) < abs(number): # 기존 연속합에 음수를 더했을 때 음수인 경우 이전의 연속합들은 이후의 연속합에 도움이 되지 않음.
maxnum = -1001 # 연속합 리셋
else: # 기존 연속합에 음수를 더했을 때 양수인 경우, 이후의 연속합에 영향을 끼칠 수 있으므로, 이전의 연속합에 이어 연산을 계속한다.
maxnum += number
else: # number가 양수인 경우 연속합 연산을 진행
maxnum = max(maxnum, maxnum+number)
lst.append(maxnum) # numbers의 마지막 값이 양수인 경우 최대값 비교를 위해 저장, 만약 이미 저장이 되어 -1001인 경우 최대값 연산에 영향을 주지 않으므로 그냥 저장.
print(max(lst))
'''
# 최초 시도 코드에 예외처리 추가(112ms)
'''
https://mygumi.tistory.com/97
예외처리1: 이전의 합이 음수라면 고려하지 않음.
예외처리2: 이전의 합과 현재의 값을 더했을 때 음수이면 고려하지 않음.
'''
N = int(input())
numbers = list(map(int, input().split()))
maxnum = numbers[0]
for i in range(1, N):
if numbers[i-1] > 0 and numbers[i-1] + numbers[i] > 0:
numbers[i] += numbers[i-1]
# maxnum = max(maxnum, numbers[i])보다 if문을 사용하는 것이 더 빠르다.
if maxnum < numbers[i]:
maxnum = numbers[i]
# print(max(numbers)) <- 두번째 if문 없이 해당 구문을 실행하는 것은 별차이가 없다.
print(maxnum)
백준 1932번: 정수 삼각형(Silver I)
'''
백준 1932번: 정수 삼각형(Silver I)
https://www.acmicpc.net/problem/1932
다이나믹 프로그래밍
프로그래머스 Lv.3과 같은 문제
https://programmers.co.kr/learn/courses/30/lessons/43105
'''
N = int(input())
triangle = []
for _ in range(N):
triangle.append(list(map(int, input().split())))
for i in range(1, len(triangle)):
for j in range(len(triangle[i])):
if j == 0:
triangle[i][j] += triangle[i-1][j]
elif j == len(triangle[i])-1:
triangle[i][j] += triangle[i-1][j-1]
else:
triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
print(max(triangle[len(triangle)-1]))
다이나믹 프로그래밍 > 개미 전사
N = int(input())
dp = [0] * N
lst = list(map(int, input().split()))
# 첫 두칸을 통해 Bottom-Up 방식의 Dynamic Programming 진행
dp[0] = lst[0]
dp[1] = max(lst[0], lst[1]) # 첫 두 칸에서는 합을 구할 수 없으니, 둘 중 최대 값으로 진행
# 이런 식으로 올라가면 이전의 최대 합과 이후의 값들을 비교하며 답을 구할 수 있음.
for i in range(2, N):
dp[i] = max(dp[i-1], dp[i-2] + lst[i]) # 이전까지의 합이 더 크냐, 이이전까지의 합과 현재 위치의 합이 더 크냐
print(dp[N-1])
다이나믹 프로그래밍 > 바닥 공사
두고 두고 다시 생각해보자…
N = int(input())
dp = [0] * N
dp[0] = 1
dp[1] = 3
for i in range(2, N):
dp[i] = (dp[i-1]+2 * dp[i-2]) % 796796
print(dp[N-1])
다이나믹 프로그래밍 > 효율적인 화폐 구성
너도 두고 두고 다시 보자..
INF = 10001
N, M = map(int, input().split())
money = []
for _ in range(N):
money.append(int(input()))
dp = [INF] * (M+1)
dp[0] = 0
# 화폐의 종류 별로 Bottom-Up DP 실행
for i in range(N):
for j in range(money[i], M+1):
if dp[j - money[i]] != INF: # 방법이 존재하는 경우
dp[j] = min(dp[j], dp[j - money[i]] + 1) # 동전의 개수가 하나씩 늘어남
print(dp[M] if dp[M] != INF else -1)