스터디룸

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #12865 평범한 배낭

문제 풀이

0-1 냅색(0-1 Knapsack) 문제라고도 부르며 대표적인 DP문제로 소개되곤 한다. 다만 그 풀이는 하위 문제 분할이 잘 생각나지 않을 수 있으므로 한 번은 짚고 넘어 가야겠다.

가방에 들어가는 짐의 개수와 무게가 주어진 제약조건을 기준으로 1씩 분할된다고 해보자.

각 짐에 대해 탐색을 진행하되 0부터 W까지 탐색한다. 탐색에 쓰이는 짐의 무게가 탐색 중인 허용치보다 작거나 같을 때 이전 짐에서 탐색한 결과와 비교하여 갱신하면 되겠다.

시간제한이 빡빡한 편이여서 풀이 자체는 정답이지만 주소 할당이나 리스트 생성에서 비효율이 발생하면 여지없이 TLE를 출력한다.

python 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
cargo = []
for _ in range(N):
    cargo.append(list(map(int, input().split())))
dp = [[0] * (K + 1) for _ in range(N + 1)]
for i in range(1, N + 1): # 각 짐에 대해
    for j in range(1, K + 1): # 각 저장용량에 대해
        if cargo[i - 1][0] <= j: # 만약 짐이 용량 이하라면
            dp[i][j] = max(
            dp[i - 1][j], # 이전 짐의 동일 허용치 값과
            dp[i - 1][c - cargo[i - 1][0]] + cargo[i - 1][1]
                # 이전 짐의 허용치-현재 짐 무게의 값 + 현재 짐 가치와 비교
            )
        else:
            dp[i][j] = dp[i - 1][j] # 용량보다 크면 이전과 값 동일
print(dp[N][K])

여기서 탐색 짐의 용량이 허용치보다 클 경우 굳이 탐색을 할 필요가 없다. 그리고 dp 배열도 굳이 2차원이 아니라 탐색 횟수는 별 차이 없겠지만 용량을 기준으로 1차원 배열로 만들 수 있을 듯 하다.

python 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
cargo = []
for _ in range(N):
    cargo.append(list(map(int, input().split())))
dp = [0 for _ in range(K + 1)] # 각 무게에 대해
for w, k in cargo:
    for c in range(K, w - 1, -1): # 마지막 용량부터 탐색 짐 무게까지
        dp[c] = max(dp[c], dp[c - w] + k) # 현재값, 용량-현재무게 + 가치
print(dp[K])

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #11053 가장 긴 증가하는 부분 수열

문제 풀이

LIS 문제 중 DP를 사용해 해결하는 가장 기초적인 문제다. 배열의 길이만큼 dp 배열을 생성해두고 i 번째 원소에 대해 최대 증가 수열의 값을 도출하면 dp의 max값이 정답이 된다.

• 초기값은 1로 설정
• i 번째는 i - 1 좌표까지의 원소들 중 자신보다 작으며 그 중 최대인 값 + 1이 된다.
• i번째 값이 산출되면 기존 최댓값과 비교, 갱신
• 순회가 모두 끝나고 최댓값 출력

python 코드

import sys

input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))
max_v = 1
dp = []
for i in range(N):
    b = 0
    for j in range(i):
        if nums[i] > nums[j]:
            b = max(b, dp[j])
    dp.append(b + 1)
    max_v = max(max_v, dp[i])
print(max_v)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #10844 쉬운 계단 수

문제 풀이

하위 문제 결과를 저장하는 배열 구성을 파악하지 못하면 해결하기 힘든 문제다. 보통 DP 배열을 1차원으로 작성하지만 이 문제는 길이 N의 계단 수를 생성할 때 길이 N - 1의 계단 수와 그 계단 수의 마지막 자리 수에 의존한다. 따라서, [길이][끝자리 수]라는 2차원 배열로 관리하며 길이 N인 계단 수는 sum(dp[N])이 될 것이다.

• dp 배열 초기화 (row = N + 1, col = 10)
• 초기 값은 dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
• 길이 2부터 만약 일의 자리 수가 0이나 9면 길이 i - 1 계단 수의 일의 자리 수가 1이거나 8이어야 한다. 나머지는 일의 자리수 k에 대해 dp[i - 1][k - 1] + dp[i - 1][k + 1]이 성립한다.
• 마지막까지 진행한 후 sum(dp[N]) 출력

python 코드

import sys

input = sys.stdin.readline

N = int(input())
dp = [[0 for _ in range(10)] for _ in range(N + 1)]
for i in range(1, 10):
    dp[1][i] = 1

for i in range(2, N + 1):
    dp[i][0] = dp[i - 1][1]
    dp[i][9] = dp[i - 1][8]
    for j in range(1, 9):
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
print(sum(dp[N]) % 1000000000)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #2156 포도주 시식

문제 풀이

i번째 잔을 마셨을 경우 얻을 수 있는 최대 총량을 dp 배열에 저장한다고 하자. 포도주를 시식하는 데 흔히 하기쉬운 실수가 i번째 잔을 마시기 전 연속된 세 개의 잔 조건만 의식하여 dp[u - 3] + w[i - 1] + w[i] 혹은 dp[i - 2] + w[i]만을 비교해 dp배열을 입력할 수 있다. 하지만 이 문제는 1칸 혹은 2칸씩 전진할 수 있다는 제약조건이 걸린 계단 문제와는 달리 3칸을 건너 뛰어도 무방하다. 따라서 dp[i - 3] + w[i - 1] + w[i]가 아니라 i - 3번째 잔까지의 dp 배열 중 최대값이어야 한다.

python 코드

import sys
input = sys.stdin.readline

N = int(input())
dp = [0] # 1번 index로 매핑하기 위함
w = [0] # 1번 index로 매핑하기 위함
for _ in range(N):
    w.append(int(input()))
dp.append(w[1]) # 1번째 잔은 무조건 마심
max_v = dp[0] # i-3번째 잔까지의 최대값 초기화
sol = dp[1] # 현재까지의 최대값
for i in range(2, N + 1):
    dp.append(max(max_v + w[i - 1] + w[i], dp[i - 2] + w[i]))
    max_v = max(max_v, dp[i - 2])
    # 3번 부터는 정상적으로 i-3번째 잔까지의 최대값 반영
    sol = max(sol, dp[-1])
print(sol)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #1463 1로 만들기

문제 풀이

특정 숫자 N을 연산하는 데 경우의 수는 세 가지이다. 시간이 0.15초로 제한인 걸 봐선 메모이제이션이 아니라 타뷸레이션으로 진행해야 하지 싶다.

1. 3으로 나누어 떨어질 경우 3으로 나눈다.
2. 2로 나누어 떨어질 경우 2로 나눈다.
3. 1을 뺀다.

• 0으로 초기화된 하위 문제를 저장할 길이가 N + 1인 dp배열 생성
• 2번부터 N까지 초기값은 dp[i - 1] + 1로 설정(연산 방법 3번)하고 3으로 나눌 수 있다면 dp[i // 3] + 1과 비교하고 2로도 나눌 수 있다면 dp[i // 2] + 1과 비교한다. 그 중의 최솟값이 dp[i]가 된다.
• 마지막까지 진행하면 dp[N]를 출력한다.

python 코드

import sys
input = sys.stdin.readline

N = int(input())
dp = [0 for _ in range(N + 1)]
for i in range(2, N + 1):
    dp[i] = dp[i - 1] + 1
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)
print(dp[N])