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차원 배열만으로도 풀수 있는 문제였따.

def LCS(a,b,c):
    global X,Y,Z
    for i in range(1,X+1):
        for j in range(1,Y+1):
            for k in range(1,Z+1):
                if a[i-1] == b[j-1] and b[j-1] == c[k-1]:
                    LCS_array[i][j][k] = LCS_array[i-1][j-1][k-1] +1
                else:
                    LCS_array[i][j][k] = max(LCS_array[i][j][k], LCS_array[i-1][j][k], LCS_array[i][j-1][k], LCS_array[i][j][k-1])

a = input()
b = input()
c = input()
X = len(a)
Y = len(b)
Z = len(c)
LCS_array = [[[0 for _ in range(Z+1)] for _ in range(Y+1)] for _ in range(X+1)]


LCS(a,b,c)

print(LCS_array[X][Y][Z])

우리가 예전에 했던 LCS를 3차원으로 늘려주면 된다. 

1차원만 더 늘려주면 되는 문제라 쉽게 풀 수 있었던 문제였다.

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
sys.setrecursionlimit(20000)


def dfs(left_idx,right_idx,day):
    if left_idx > right_idx:
        return 0
    if dp[left_idx][right_idx] != -1:
        return dp[left_idx][right_idx]

    dp[left_idx][right_idx] = max(dp[left_idx][right_idx], dfs(left_idx+1,right_idx,day+1) + v[left_idx]*day , dfs(left_idx,right_idx-1,day+1) + v[right_idx]*day)
    return dp[left_idx][right_idx]
def input():
    return sys.stdin.readline().rstrip()

N = int(input())

v = [int(input()) for _ in range(N)]

dp = [[-1 for _ in range(N)] for _ in range(N)]


print(dfs(0,N-1,1))

처음 풀었던 방식은 재귀를 이용해서 풀었다. 재귀는 다음과 같다.

left_idx는 현재 왼쪽 논 밭의 위치 right_idx는 오른쪽 논 밭의 위치를 나타낸다. 그리고 day는 현재의 날짜를 나타낸다.

left_idx> right_idx를 넘어가면 0을 return 해준다.

그리고 dp에서 초기값이 아니면 저장된 값을 해준다.

우리는 생각해보면 둘 중 하나를 선택해야한다. 여기서 왼쪽을 먼저 벨지 오른쪽을 먼저 벨지이다.

이 두가지 경우에 대해 재귀를 돌리고 그 결과 중 max값을 현재의 dp에 저장해주면 된다.

 dp[left_idx][right_idx] = max(dp[left_idx][right_idx], dfs(left_idx+1,right_idx,day+1) + v[left_idx]*day , dfs(left_idx,right_idx-1,day+1) + v[right_idx]*day)

현재 저장된 값과 왼쪽을 먼저 갔을때 오른쪽을 먼저깟을때를 구분해서 재귀를 돌려주면 된다.

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
v = [0]+[int(input()) for _ in range(N)]

dp = [[v[i] *N  if i == j else 0 for i in range(N+1)] for j in range(N+1)]



for y in range(1,N+1):
    for x in range(y-1,0,-1):
        dp[x][y] = max(dp[x+1][y] + v[x] * (N - y + x), dp[x][y-1] + v[y]*(N-y+x))

print(dp[1][N])

두번쨰는 재귀 대신 반복문을 이용해서 푸는 방식이다.

여기서 dp 테이블의 뜻은 x에서 y까지 베었을때의 최대값이다.

먼저 dp를 초기화 시켜줘야한다. 초기화 시켜줄때 i와 j 가 같을때에는 v[i] * N을 해준다.

그 이유는 i번째에서 j번째까지 같을 때 최대값이 되는 경우는 가장 마지막 날에 이 벼를 베는 것이다.

그러므로 이 값으로 초기화를 해준다.

첫번째 풀이는 바깥에서 안쪽으로 베어나가는 느낌으로 풀었다면, 이 풀이는 안쪽에서 바깥쪽으로 베어나가는 느낌으로 푸는 방식이다.

x ->y까지 베었을때의 최대값이 나올 수 있는 경우의 수는

x+1~y를 남겨두고 x를 베었을 때

아니면 x~y-1 를 남겨두고 y를 베었을 때 이다.

그러면 우리는 dp[x+1][y] + v[x] * (N - y + x) 와 dp[x][y-1] + v[y] * (N -y +x)를 비교를 해서 최대값을 저장해주면 된다.

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().rstrip()
while True:
    N,M = map(int,input().split())
    if not N+M:
        break
    dp = [[0 for _ in range(M+1)]]

    for _ in range(N):
        temp = [0]+list(map(int,input().split()))
        dp.append(temp)
    result = 0
    
    for x in range(1,N+1):
        for y in range(1,M+1):
            dp[x][y] = min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1]) + 1 if dp[x][y] else 0

            if result<dp[x][y]:
                result = dp[x][y]
    print(result)

이 문제는 유명한 문제이다. 원래 행렬에서 최상단과 좌측에 0인 배열을 넣어주고, 탐색을 해주면 된다.

그리고 (x-1,y), (x,y-1), (x-1,y-1) 의 최소값에 + 1을 해준다. 만약 dp[x][y]에 1이 있을 경우에만

그렇지 않을때에는 0을 넣어주면 된다.

그리고 탐색을 하면서 최대값을 갱신해주면 된다.

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 만 곱해진 동전이기 때문이다.