[알고리즘] DP(Dynamic Programming) - 백준 17202 9655 2579 2156 2565 1967 3020

다이나믹 프로그래밍

효율적인 알고리즘을 위해 사용할 수 있는 기법. top-down(메모이제이션, 하향식) / bottom-up(상향식) 방식이 있다.

간단하게 설명하면 문제를 작은 문제부터 해결하여 큰 문제의 답을 도출하는 방식.

 

백준 17202 핸드폰 번호 궁합

a = list(input()) 
b = list(input())  
data = []
for i in range(len(a)):
    data.append(a[i])
    data.append(b[i])
dp = [0 for _ in range(15)]
 
for i in range(len(data)-1):
    dp[i] = (int(data[i]) + int(data[i+1])) % 10
 
for i in range(14, 1, -1):
    for j in range(i):
        dp[j] = (dp[j] + dp[j+1]) % 10
 
ans = str(dp[0]) + str(dp[1])
 
print(ans)

 

백준 9655 돌 게임

n = int(input())
 
if n % 2 == 1:
    print('SK')
else:
    print('CY')

엄..?

 

백준 2579 계단 오르기

 

n = int(input())
 
score = []
 
for _ in range(n):
    score.append(int(input()))
    
dp = [0] * n
 
if n <= 2:
    print(sum(score))
    
else:
    dp[0] = score[0]
    dp[1] = dp[0] + score[1]
    dp[2] = max(dp[0] + score[2], score[1] + score[2])
    
    for i in range(3, n):
        dp[i] = max(dp[i-3] + score[i-1] + score[i], dp[i-2] + score[i])
        
    print(dp[-1])

 

백준 2156 포도주 시식

n = int(input())
 
alcohol = []
 
for _ in range(n):
    alcohol.append(int(input()))
 
dp = [0] * n
 
if n <= 2:
    print(sum(alcohol))
else:
    dp[0] = alcohol[0]
    dp[1] = dp[0] + alcohol[1]
    dp[2] = max(dp[0] + alcohol[2], alcohol[1] + alcohol[2])
    for i in range(3, n):
        dp[i] = max(dp[i-3] + alcohol[i-1] + alcohol[i], dp[i-2] + alcohol[i], dp[i-4] + alcohol[i-1] + alcohol[i])
        
    print(max(dp))

 

백준 2565 전깃줄

n = int(input())
 
elec = []
 
for _ in range(n):
    a, b = map(int,input().split())
    elec.append((a,b))
 
elec.sort(key = lambda x:x[0])
 
dp = [0] * n
 
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if elec[j][1] < elec[i][1]:
            dp[i] = max(dp[i], dp[j] + 1)
            
print(n - max(dp))

점화식 잘 세우는게 좀 어렵긴하다. 학생 때도 점화식 진짜 싫어했었는데 결국 만나게 되어버린...

 

 

백준 1967 트리의 지름

이거 넘 어렵다... 나중에 다시 봐야될듯 구글링 해서 풀었음

 

from collections import deque
 
n = int(input())
 
graph = [[] for _ in range(n+1)]
 
 
def bfs(start):
    visited = [-1] * (n+1)
    visited[start] = 0
    q = deque()
    q.append(start)
    while q:
        c = q.popleft()
        for no, w in graph[c]:
            if visited[no] == -1:
                q.append(no)
                visited[no] = visited[c] + w
                
    m = max(visited)
    return [visited.index(m), m]
 
 
 
for _ in range(n-1):
    start, end, weight = map(int, input().split())
    graph[start].append([end, weight])
    graph[end].append([start, weight])
    
print(bfs(bfs(1)[0])[1])

 

 

 

백준 3020 개똥벌레

 

머리가~ 안돌아가~

n, h = map(int, input().split())
 
up = [0] * (h+1)
down = [0] * (h+1)
 
for i in range(n):
    if i%2 == 0:
        down[int(input())] += 1
    else:
        up[int(input())] += 1
        
for i in range(h-1, 0, -1):
    down[i] += down[i+1]
    up[i] += up[i+1]
    
min_val = n
min_cnt = 0
 
for i in range(1, h+1):
    x = down[i] + up[h-i + 1]
    if x < min_val:
        min_cnt = 1
        min_val = x
    elif x == min_val:
        min_cnt += 1
print(min_val, min_cnt)