Coding 공부

DP 문제 테이블 방식은 2종류

dp[a][b] = a번의 횟수와 b의 높이가 남았을때의 최저 시도횟수

dp[a][b] = min(dp[a][b], 1 + max(dp[a-1][t-1], dp[a][b-t]))

1~b 사이에서 떨어드렸을 때, 깨지는 경우와 안깨지는 경우의 최악의 경우 max값을 구하고, 거기에 +1을 해준다.

횟수가 1회 남았을시에는 무조건 높이만큼의 횟수가 필요하니 그에 맞게 초기화

 횟수와 상관없이 1층만 남았을때에는 1회로 끝낼수 있으니 그걸로 초기화

다른 dp식 cozyyg 님의 코드를 보고 복기한거 틀릴 수 도 있음

dp[x][y] = x번 던질 기회가 남았을때 y번 시도해서 알 수 있는 유리가 깨지는 최소 높이

dp[x][y] = dp[x][y-1] + dp[x-1][y-1] + 1

y-1번을 시도했을때 x번 던질기회가 남았을때의 값과 ( 즉 깨지지 않았을때와) y-1번을 시도해서 x-1번 던질 기회가 남았을때(깨졌을때를 하면) 이 때의 최소높이는  이 두값을 더하고 + 1을 해준다.

두번째는 제대로 해석했는지는 모르겠다. 

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
 
N,W = map(int,input().split())
 
 
dp = [[0 for _ in range(W+1)] for _ in range(N)]
 
first = int(input())
 
if first == 1:
    dp[0][0] = 1
else:
    dp[0][1] = 1
 
 
for ind in range(1,N):
    num = int(input())
    num -= 1
    dp[ind][0] = dp[ind-1][0]
    if not num:
        dp[ind][0] += 1
    for j in range(1,W+1):
        dp[ind][j] = max(dp[ind-1][j],dp[ind-1][j-1])
        if j%2 == num:
            dp[ind][j] += 1
 
print(max(dp[N-1]))

다이나믹 프로그래밍을 이용한 문제였다.

2차원 배열 dp을 정의했다.

dp[N][W] 는 n번째일때의 w 번 이동했을때의 최대값인 경우로 dp 배열을 정의했다.

그러면 dp[n][w]일때의 값은 dp[n-1][w-1] 이나 dp[n-1][w]의 최대값이 될것이다. 이동을 했거나, 이동을 하지 않았거나 이다.

그리고 짝수번을 움직였을때에는 무조건 1번 나무에 있고, 홀수번을 움직였을때에는 무조건 2번나무에 위치해있는다.

이점을 이용해

dp[n][w] = max(dp[n-1][w-1],dp[n-1][w])을 비교해주고,

현재 떨어진 과일나무의 위치와 움직인 횟수의 홀수짝수가 동일 할 때에는

해당 위치에서 현재 떨어지는 열매를 먹을수 있는것이므로, 1개씩 더해주면 된다.

dp배열을 정의하고, 움직인 횟수가 홀수 짝수일때를 비교를 해, 1번나무에 위치해있는지,

2번나무에 위치해있는지를 구분해주면, 3차원 배열을 쓰지 않고도, 2차원 배열만으로도 풀수 있는 문제였따.

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()
 
max_coins = 50000
for _ in range(3):
    N = int(input())
    coins = defaultdict(int)
    dp = [0 for _ in range(max_coins+1)]
    dp[0] = 1
    total_sum = 0
    for _ in range(N):
        coin,cnts = map(int,input().split())
        for cur_coin in range(max_coins,coin-1,-1):
            if dp[cur_coin - coin]:
                for cnt in range(cnts):
                    next_coin = cur_coin + coin * cnt
                    if 0<=next_coin<=max_coins:
                        dp[next_coin] = 1
        total_sum += coin*cnts
 
    if total_sum%2 or not dp[total_sum//2]:
        print(0)
    else:
        print(1)

이 문제를 풀때 어려움을 많이 겪었다.

이 문제를 처음 푼 방식은 다음과 같다. dp는 동전을 만들수 있는 경우의 수이다.

먼저 dp[0]은 1로 초기화 해준다.

그리고 각 입력이 들어올때마다 dp를 max_coin에서 현재 들어온 동전인 coin 까지 반복문을 돌면서

cur_con - coin의 위치에 dp의 값이 존재하면, 만들 수 있는 경우의 수가 있으므로,

여기서 부터 다시 동전의 개수만큼 더해주면서 dp를 채워주면 된다.

이렇게 dp를 채워준 뒤에 전체 동전을 total_sum에 더해준다.

이렇게 한뒤에 만약 홀수 이거나 dp[total_sum//2]의 값이 존재하지 않으면 0을 출력한다.

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()
 
def solution():
    N = int(input())
    coins = []
    total_coins = 0
    for _ in range(N):
        a,b = map(int,input().split())
        coins.append((a,b))
        total_coins += a*b
    if total_coins%2:
        return 0
    else:
        find_coin = total_coins//2
        dp = [0 for _ in range(find_coin+1)]
        dp[0] = 1
        coins.sort(key= lambda x : -x[1])
        acc_coins = 0
        for coin,cnts in coins:
            max_coin = coin*cnts
            for i in range(min(max(acc_coins,max_coin),find_coin),coin-1,-1):
                if dp[i-coin]:
                    for cnt in range(cnts):
                        next_coin = coin*cnt + i
                        if 0<=next_coin<=find_coin:
                            dp[next_coin] = 1
            if dp[find_coin]:
                return 1
            acc_coins += max_coin
        return 0
for _ in range(3):
    print(solution())

이 풀이는 좀 더 빠르대신 좀 더 복잡하다. 위에서는 고정된 최대값 50000에서부터 하나하나씩 찾는거라 하면,

이 풀이는 이 코인에서 가능한 최대값에서부터 하나씩 내려가는 것이다.

탐색이 가능한 최대 범위는 acc_coins 누적된 값 아니면 max_coin 중 더 큰 값에서부터 하나씩 내려가야한다.

우리는 dp[i - coin] coin 단 1개를 빼서 존재했을때부터 해당 동전이 가지는 개수를 갱신해주기 때문이다.

여기서 또 주의해야할 점은 위의 최대값이 find_coin을 넘어갈순 없다. 그러므로 둘중 min값 부터 시작해주면 된다.

import sys
def input():
    return sys.stdin.readline().rstrip()
 
 
 
N,M = map(int,input().split())
MA = [0]+list(map(int,input().split()))
WA = [0]+list(map(int,input().split()))
MA.sort()
WA.sort()
 
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
 
 
for x in range(1,N+1):
    for y in range(1,M+1):
        if x == y:
            dp[x][y] = dp[x-1][y-1] + abs(MA[x]-WA[y])
        elif x>y:
            dp[x][y] = min(dp[x-1][y-1] + abs(MA[x]-WA[y]), dp[x-1][y])
        else:
            dp[x][y] = min(dp[x-1][y-1] + abs(MA[x]-WA[y]), dp[x][y-1])
 
print(dp[N][M])

이 문제는 성격의 차이의 합이 최소가 되도록 커플을 하는 것이다.

이 문제를 푸는 방식은 다음과 같다.

2차원 DP를 설정하고,  행은 남자 열은 여자를 뜻하는 것으로 하고,

x,y 까지 커플을 했을때, 최소 성격차를 저장했다고 하자.

이 문제는 사실 boj.kr/13398 하고 비슷하다고 생각한다.

만약 x == y가 같다면, 전부 커플이 되어야하기 때문에

dp[x][y] = dp[x-1][y-1] + abs(MA[x] - WA[y]) 가 되어야한다.

만약 x> y이면 우리는 남자는 커플이 될수도, 커플이 안될수 도 있다. 그러면 우리는 이중 최소값을 구해야한다.

이 남자가 커플이 된다하면. 위와 동일하게 dp[x-1][y-1] + abs(MA[x] -WA[y])와 동일하다.

이 남자가 커플로 선택되지 않으면, 이 남자의 성격은 그대로 버려지고, 이 남자가 솔로가 됬으므로, dp[x-1][y]와 동일하다.

이 2개의 값을 비교해서 최소값을 dp[x][y]에 넣어주면 된다.

x<y 일때는 여자가 더 많은 것이므로 위와 동일하게 하지만 x,y 만 바꿔주면 된다.

그리고 결과 적으로 dp[N][M}을 출력 해주면 된다.

여기서 좀 더 쉽게 풀기 위해서 남자 성격과 여자 성격의 list를 앞에 [0]을 넣어줘서 index를 편하게 해주었다.

import sys
 
def input():
    return sys.stdin.readline()
 
N = int(input())
INF = float('inf')
dp = [INF for _ in range(101)]
dp[2] = 1
dp[3] = 7
dp[4] = 4
dp[5] = 2
dp[6] = 6
dp[7] = 8
dp[8] = 10
 
for num in range(9,101):
    for i in range(2,8):
        if i != 6:
            dp[num] = min(dp[num],dp[num-i]*10+dp[i])
        else:
            dp[num] = min(dp[num],dp[num-i]*10)
for _ in range(N):
    k = int(input())
    
    max_value = ('7' if k%2 else '1' ) +'1'*(k//2-1)
    print(dp[k],max_value)

이 문제를 푸는 방식은 다음과 같다.

2개부터 8개까지의 성냥개비를 이용해서 만들 수 있는 최소의 수가 있다.

먼저 이 수들을 각각 저장을 해주는 것이다.

단 여기서 주의해야할 점은 성냥개비의 개수가 6개일때다.

6개일때는 원래 최저의 수는 0이지만, 자리수가 1개일때 0이 올수가 없다. 이 점만 주의해주면 된다.

이렇게 2~8개의 최소 숫자를 구해주고

9개부터는 그리디하게 찾아주면 된다.

dp [ 현재 성냥의 개수 - i개 ] *10 + dp[i] 와 dp[현재 성냥의 개수] 의 최소값을 비교해서 갱신해주면 된다.

그리고 위에 말했듯이 6개일때는 가장 작은 수는 0 이므로 *10만 해주면 된다.

이렇게 최소 숫자를 구했으면,

최대 숫자를 구해야한다.

여기서 가장 큰 숫자를 만드는 법은 가장 적은 개수로 만들수 있는 1로 채우는 것이다.

그런데 이럴때 문제는 성냥의 개수가 홀수일때 문제가 된다.

성냥의 개수가 홀 수 일때 1개가 남아서, 어떠한 숫자도 만들수 없다.

그러므로 주어진 성냥개비의 숫자가 홀수이면, 가장 앞의 수를 1이 아닌 성냥개비 3개로 만들수 있는 가장 큰수를 만들어줘야한다.

그에 부합하는 숫자는 7 이므로,

주어진 성냥 개비의 숫자가 홀수이면 7 아니면 1을 붙이고, 성냥개비를 2로 나눈 몫에서 1을 뺀숫자만큼 붙여주면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
T = int(input())
dp = [i for i in range(101)]
 
for i in range(100):
    for coin in [10,25]:
        if i +coin > 100:continue
        dp[i+coin] = min(dp[i+coin],dp[i]+1)
for _ in range(T):
    N = int(input())
 
    answer = 0
    while N>0:
        answer += dp[N%100]
        N//=100
    print(answer)
 
 
 

이 문제는 100까지의 최소 코인의 개수를 구해준 뒤에, 100단위로 나눠주면서 그 개수를 더해주면 된다.

왜냐하면

이 문제에서 쓰이는 동전은 [1,10,25]로 되어있고

각 100^k 만 곱해진 동전이기 때문이다.

import sys
sys.setrecursionlimit(20000)
def input():
    return sys.stdin.readline().rstrip()
def trace(cur_node,prev_check):
    visited[cur_node] = False
    flag = 0
    if not prev_check:
        if dp[cur_node][0] < dp[cur_node][1]:
            result.append(cur_node)
            flag = 1
    for next_node in graph[cur_node]:
        if visited[next_node]:
            trace(next_node,flag)
 
def dfs(node):
    visited[node] = False
    child_node = []
    for next_node in graph[node]:
        if visited[next_node]:
            child_node.append(next_node)
    if not len(child_node):
        dp[node][1] = arr[node]
 
        return
    else:
        dp[node][1] += arr[node]
        for child in child_node:
            dfs(child)
            dp[node][0] += max(dp[child][1],dp[child][0])
            dp[node][1] += dp[child][0]
 
 
 
N = int(input())
arr = [0] + list(map(int,input().split()))
 
# 1이 선택 
# 0이 선택 x
dp = [[0 for _ in range(2)] for _ in range(N+1)]
 
graph = [[] for _ in range(N+1)]
visited = [True for _ in range(N+1)]
for k in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
 
 
dfs(1)
 
print(max(dp[1]))
 
 
result = []
visited = [True for _ in range(N+1)]
trace(1,0)
result.sort()
print(*result)

어려웠던 문제였다. 트리dp를 활용해서 최적의 경우를 찾는 것은 많았지만, 그 최적을 만족하는 것을 trace를 하는 문제는 처음이라 푸는데 오래걸렸다.

dp라는 테이블을 만들고 (N+1)*2의 배열을 만들어 두었다.

여기서 1은 해당 노드를 선택했을때의 최대값

0은 해당 노드를 선택하지 않았을때의 최대값이다.

만약 리프노드이면 자신을 선택하는 조건이외에는 없을것이다.

그러므로 dp[leef_node][1] = arr[leef_node]를 넣어준다.

리프노드를 제외한 나머지 노드들은 0번 인덱스와 1번인덱스의 최대값을 구해야한다.

현재 노드를 선택했을때 즉 1번인덱스에는

현재 노드를 cur_node라고 했을때 arr[cur_node]를 더해줘야할것이다.

그리고 현재 노드를 선택했으므로, 자식노드들은 선택을 하지 못한다.

그러므로 dp[cur_node][1] += dp[child_node][0] 와 같이

자식 노드들의 선택하지않았을때의 값들을 전부 더해줘야한다.

그리고 현재 노드를 선택하지 않았을때에는

자식 노드를 선택하던지, 선택하지 않는것은 마음대로 할 수 있다.

그러므로 둘중 더 큰 값을 더해주면 된다.

이렇게 dp에 값을 누적시켜서 구하면

우리는 1번노드로 시작했기 때문에

1번노드의 dp에서 최대값을 구할 수 있다.

그러면 우리는 이 dp에서 어떤 노드들이 선택됬는지를 찾아봐야한다.

우리는 이전 노드에서 선택했는지 안했는지에 따라, 현재 노드를 선택할수 있는지 아닌지가 결정이 된다.

그래서 우리는 prev_check를 통해 문제를 해결했다. 위와 동일하게 하기 위해서 0일때에는 부모노드를 선택하지 않았다.

1일때에는 부모노드를 선택했다이다.

만약 부모노드를 선택하지 않았을때에는, 우리는 지금 있는 현재노드를 선택할지 안할지를 결정지을수 있다.

그 결정방법은 dp에 저장된 값을 비교를 해서, 우리가 선택하지 않았을때보다 선택했을때의 값이 더 크면,

그때 현재노드를 선택을 하고, flag를 1로 바꿔준다. 현재노드를 선택을 했으므로, result에 추가 시켜준다.

그리고 재귀를 통해 모든 노드들에 대해 탐색을 해주면 된다.

이 문제는 최대값을 구하는 것 뿐만 아니라, 그 경우의 수가 만들어지는 것을 찾는데 더 어려움을 겪었다.

트리 dp와 관련된 문제들을 좀 더 연습해야겠다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
def dfs(idx):
    if idx >= N:
        return 0
 
    if dp[idx] != -1:
        return dp[idx]
    max_value = 0
    for string_key in score_dict.keys():
        score,len_string = score_dict[string_key]
        if idx + len_string-1<N:
            for check_idx in range(len_string):
                if input_string[check_idx+idx] != string_key[check_idx]:
                    break
            else:
                max_value = max(max_value,score + dfs(idx+len_string))
    max_value = max(max_value,1+dfs(idx+1))
    dp[idx] = max_value
    return dp[idx]
                
 
input_string = input()
N = len(input_string)
M = int(input())
score_dict = {}
for _ in range(M):
    string,score = input().split()
    score_dict[string] = [int(score),len(string)]
 
 
 
dp = [-1]*(N+1)
 
print(dfs(0))

문제를 푼 방식은 다음과 같다.

문제에 주어진 문자열들을 문자열을 key로 하고, 점수와 길이를 value로 하는 dictionary에 넣어둔다.

그리고 0번인덱스부터 재귀를 돌면서

현재 위치에서부터 문자열이 일치하는 경우에 재귀를 하면서 최대값을 구한다.

그리고 일치하지 않을때를 위해, dfs(idx+1)+1 현재위치의 문자열만을 제거했을때도 구해주면된다.

그리고 dp값을 변환시켜주면 된다.