100년 뒤 개발자 한승규입니다.

https://www.acmicpc.net/problem/2293

별로 어렵다고 생각하지 않았지만, 풀다보니 굉장히 어려운 문제였다.

단순하게 배열로 쭉 만들어서 더하며 나가면 된다고 생각했는 데, 구성이 같은 것들을 제외하느라 시간을 오래쓰게 되었다.

이해가 잘 될 수 있도록 보기를 통해 분석해보도록 하자.

보기는 1, 2, 5이 3가지 동전으로 10을 채우는 경우를 구하는 것이다.

경우의 수를 모두 구해보자.

이렇게 10가지의 경우가 나오게된다.

이렇게보면 나누기로도 구할 수 있을 거 같은데, 일단 당연히 DP로 풀어야 하기에 생각해보지 않았다.

경우의 수가 중복이 되면 안되기 때문에 각 코인은 한 번씩 코인의 개수만큼 반복해야 한다.

일단 코인을 입력받으면, 해당 코인의 가치만큼의 경우의 수가 +1 되는 것이다.

그리고 1부터 목표가치만큼 진행하며, 만약 m의 가치의 경우의 수가 3이라면 m+(코인의 가치)의 가치에 해당하는 경우의 수도 3 늘어나게 되는 것이다.

이렇게 반복문을 진행해가면 된다.

import sys

n, k = map(int, sys.stdin.readline().split())

value = [0 for i in range(k+1)]

for i in range(n):
    coin = int(sys.stdin.readline().strip())
    if coin <= k:
        value[coin] += 1
    for t in range(1, (k+1) - coin):
        value[t+coin] += value[t]

print(value[-1])

https://www.acmicpc.net/problem/1932

일단 문제가 DP이기 때문에 보자마자 단계가 있는지 확인한다.

일단 바로 각 층으로 단계를 구별할 수 있을 것 같다.

그렇게 단계를 나누면, 각 단계별로 영향을 받는 것은 해당 단계의 전 단계이다.

전 단계를 보고 해당 단계의 최대값을 구하며 내려가면 될 것 같다.

import sys

n = int(sys.stdin.readline())

max_list = [0 for i in range(n)]

for i in range(n):
    level = list(map(int, sys.stdin.readline().split()))
    cur_max_list = list()

    for t in range(i+1):
        if t == 0:
            cur_max_list.append(max_list[0] + level[0])
        elif t == i:
            cur_max_list.append(max_list[-1] + level[i])
        else:
            cur_max_list.append(max(max_list[t-1], max_list[t]) + level[t])
    max_list = cur_max_list

print(max(max_list))

각 층의 첫 번째 칸과 마지막 칸은 경우가 그냥 하나 밖에 존재하지 않는다.

그냥 위의 칸 + 현재 칸이다.

해당 값은 그냥 바로 구해서 넣어줄 수 있도록 하고, 그 사이의 칸들은 윗 단계에서 내려올 수 있는 2가지 수 중에서 큰 값을 가져와 본인의 수와 더해 최대값을 구할 수 있도록 하였다.

https://www.acmicpc.net/problem/1149

이번주도 DP가 주제이다.

DP = 단계별로 값을 저장이기 때문에 문제를 보자마자

한 줄마다 각 단계를 어떻게 저장할 수 있을지를 먼저 생각해보았다.

일단 각 줄마다 영향을 받는 것은 해당 줄의 전 줄이다.

만약 3번째 줄을 본다면, 2번째 줄의 집에만 영향을 받고 1번째 줄의 집에 색에는 영향을 받지 않는다.

그럼 한 줄씩 진행해가며, 전 단계의 집을 살핀 후 각 색마다 만들 수 있는 최소 비용을 구한다.

그렇게 한 단계씩 DP를 진행해가며, 마지막에는 그 중에서 최소값을 구해 출력하게 된다.

import sys

N = int(sys.stdin.readline())

min_list = [0 for i in range(3)]

for i in range(N):
    color = list(map(int, sys.stdin.readline().split()))
    min_list = [
        min(min_list[1], min_list[2]) + color[0],
        min(min_list[0], min_list[2]) + color[1],
        min(min_list[0], min_list[1]) + color[2]
    ]

print(min(min_list))

https://www.acmicpc.net/problem/9251

옛날에 굉장히 고생했었던 LCS이다.

그 기억 때문에 이번 동적 프로그래밍에서 이번 문제를 뽑은 거 같기도 하다.

당연히 동적 프로그래밍답게 배열이 등장한다.

하지만 여기서는 기존과는 다르게 2차원 배열이다.

이 생각을 못해서 옛날에 굉장히 고생했었다.

일단 이런 식의 배열을 생성한다.

구하는 방식은 ACAYKP로 문자열을 기준 잡고

C, CA, CAP, CAPC, CAPCA, CAPACK를 순서대로 비교해가며 가장 긴 공통 수열을 찾아가는 방식이다.

각 문자열의 가장 앞에는 빈 문자열을 둔 것이고, 당연히 빈 문자열이기 때문에 공통 수열의 길이는 0이다.

우선 C부터 비교를 해보자

가장 긴 공통 수열은 C 하나 일 것이다.

그러면 ACAYKP에서 C 이후로는 가장 긴 공통 수열의 길이가 1이 될 것이다.

그 후로는 A를 비교해본다.

현재 비교하는 문자열은 CA이다.

ACA 이후로는 CA가 겹치기 때문에 가장 긴 공통 수열의 길이는 2가 된다.

마지막으로 CAP까지만 비교해보자.

CAP가 겹치기 때문에 길이는 3이 나오게 된다.

여기서 배열은

만약 해당 문자가 같을 경우(first_word[i] == second_word[t])에는 dp[i][t] = dp[i-1][t-1] + 1을 저장해주고

만약 해당 문자가 다른 경우(first_word[i] != second_word[t])에는 do[i][t] = max(dp[i][t-1], dp[i-1][t])로 저장해주면 된다.

그렇게 만들어진 최종 배열이다.

만들어진 코드는 다음과 같다.

import sys

first_word = list(sys.stdin.readline().strip())
second_word = list(sys.stdin.readline().strip())

max_length = max(len(first_word), len(second_word))

dp = [[0 for i in range(max_length + 1)] for t in range(max_length + 1)]

for i in range(len(first_word)):
    for t in range(len(second_word)):
        if first_word[i] == second_word[t]:
            dp[i][t] = dp[i-1][t-1] + 1
        else:
            dp[i][t] = max(dp[i][t-1], dp[i-1][t])


print(dp[len(first_word) - 1][len(second_word) - 1])

https://www.acmicpc.net/problem/11053

실버 2이지만 생각보다 오래걸렸다.

이 방법으로 푸는 게 아닌거라고는 알고 있지만, 어떻게든 풀어는 보았다.

DP인 만큼 일단 기억할 배열을 만든다.

result = [[None] for i in range(N)]

그리고 2중 반복문으로 해당 수로 만든 수열과 DP에 기억된 수열 중 최대 값이 본인보다 작은 수열 중에서 길이가 더 긴 수열로 본인 차례의 가장 긴 수열을 만들고, 마지막 결과에서 그 수열 중에서 길이가 가장 긴 수열의 길이를 출력하는 것이다.

import sys

N = int(input())

A = list(map(int, sys.stdin.readline().split()))

result = [[None] for i in range(N)]

for i in range(N):
    cur_list = [A[i]]
    for t in range(i):
        if A[i] > A[t]:
            if len(cur_list) < len(result[t]) + 1:
                cur_list = result[t] + [A[i]]
    result[i] = cur_list

result.sort(key= lambda x : len(x))

print(len(result[-1]))

https://www.acmicpc.net/problem/12865

DP에서 중요하다고 생각되는 내용 중 하나인 배낭 문제이다.

import sys

N, K = map(int, sys.stdin.readline().split())
dp = [[0] * (K + 1) for i in range(N + 1)]
thing = [[0, 0]]

for i in range(N):
    thing.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, N + 1):
    w = thing[i][0]
    v = thing[i][1]
    for t in range(1, K + 1):
        if t < w:
            dp[i][t] = max(dp[i-1][t], dp[i][t-1])
        else:
            dp[i][t] = max(dp[i-1][t], dp[i][t-1],dp[i-1][t-w] + v)



print(dp[-1][-1])

옛날에 풀었던 코드이다.

너무 오래 전이라 기억도 안나고, 이번 주 과제이기 때문에 다시 풀어보도록 했다.

우선 DP 답게 기억할 배열이 필요하다.

범위는 무게인 0부터 W까지이다.

이제는 후보들을 반복문으로 돌면서 넣을지 말지를 판단해야 한다.

해당 짐이 들어갈 수 있는 모든 구간에 대해서, 현재 넣을 후보와 이 짐을 넣었을 때의 가치를 비교하고 무엇을 넣을지를 결정하면 된다.

import sys

N, K = map(int, sys.stdin.readline().split())

candidate_weight = []
candidate_value = []

for i in range(N):
    W, V = map(int, sys.stdin.readline().split())
    candidate_weight.append(W)
    candidate_value.append(V)

result = [0 for i in range(K + 1)]

for i in range(N):
    for t in range(candidate_weight[i], K + 1):
        result[t] = max(result[t], result[t-candidate_weight[i]] + candidate_value[i])

print(result[-1])

그래서 당연히 아무 생각없이 이렇게 코드를 만들었었다.

당연히 에러가 발생한다.

만약 가능한 무게가 8이고 4인 짐을 넣으려고 하면

[0, 0, 0, 0, 4, 0, 0, 0, 8] 이렇게 하나의 짐이 2번 들어가기 때문에 안쪽에 있는 반복문은 증가하는 방향이 아니라 감소하는 방향으로 만들어주어야 한다.

import sys

N, K = map(int, sys.stdin.readline().split())

candidate_weight = []
candidate_value = []

for i in range(N):
    W, V = map(int, sys.stdin.readline().split())
    candidate_weight.append(W)
    candidate_value.append(V)

result = [0 for i in range(K + 1)]

for i in range(N):
    for t in range(K, candidate_weight[i] - 1, -1):
        result[t] = max(result[t], result[t-candidate_weight[i]] + candidate_value[i])

print(max(result))

https://www.acmicpc.net/problem/11726

DP 문제가 DP로 풀어야 한다는 것을 알고 시작하면, 별로 어려운 거 같지는 않다.

하지만 보통 시간에 막히고 그 때서야 깨닫게되어서 문제이지만...

간단하게 보면 타일은 세로로 1칸 차지하거나, 가로로 2개를 사용해서 2칸 차지하는 2가지 방법 밖에 없다.

결국 n-2일 때의 타일에 가로로 2칸 차지해서 만드는 경우와 n-1일 때 세로로 1칸 차지해서 만드는 경우를 더해주면 된다.

import sys

n = int(sys.stdin.readline())

square = [1 for i in range(n + 1)]

for i in range(2, n + 1):
    square[i] = square[i-1] + square[i-2]

print(square[-1] % 10007)

https://www.acmicpc.net/problem/2193

일단 동적프로그래밍이다.

조건으로 N이 90까지 주어지는 데, 이거를 직접 10 ** N 이렇게 구하는 건 말도 안된다는 것은 바로 알 수 있었다.

그러고는 예시를 먼저 보자.

1로 끝나는 수 뒤에는 1이 오지 못하고 0만 올 수 있다.

하지만 0으로 끝나는 수 뒤에는 1과 0이 다 올 수 있다.

그러면 N+1에서 1로 끝나는 수의 숫자는 N에서 0으로 끝나는 수의 숫자 일 것이고, 0으로 끝나는 수의 숫자는 N에서 0으로 끝나는 수와 1로 끝나는 수의 합 일 것이다.

이 생각을 바탕으로 N=1일 때의 값은 넣어주고, 입력값 N의 답을 얻을 수 있도록 하였다.

import sys

N = int(sys.stdin.readline())

end_zero = 0
end_one = 1

for i in range(N-1):
    end_zero, end_one = end_zero + end_one, end_zero

print(end_zero + end_one)