악곱 == 악성곱슬

1로 만들기

---

• 5로 나누기, 3으로 나누기, 2로 나누기, 1로 빼기 의 연산을 사용해서 가장 적은 횟수로 1을 만들기

해당 문제는 잘 알려진 다이나믹 프로그래밍 문제이다. 해당 문제가 다이나믹 프로그래밍 이유는, 해당 문제를 재귀로 구현했을 경우 함수 호출 트리를 그려보면 파악할 수 있다. 부분문제에 대한 값이 상위 결과에 영향을 미치기 때문에 다이나믹 프로그래밍으로 구현할 수 있다.

아래 코드는 바텀-업 방식으로 DP테이블을 활용하여 구현한 코드이다.

import sys

def solution(x):
    table = [0] * (x+1)
    table[2] = 1
    for i in range(3, x+1):
        table[i] = table[i-1] + 1
        if i % 5 == 0:
            table[i] = min(table[i], table[i//5] + 1)
        if i % 3 == 0:
            table[i] = min(table[i], table[i//3] + 1)
        if i % 2 == 0:
            table[i] = min(table[i], table[i//2] + 1)
    return table[x]

if __name__ == "__main__":
    X = int(sys.stdin.readline().rstrip())
    print(solution(X))

개미 전사

---

DP문제는 DP인지 판별하는 능력, 점화식을 도출하는 능력 2가지가 필요하다.

왼쪽부터 차례대로 식량 창고를 턴다고 가정할 경우 지금 당장 털 것인지, 안 털 것인지에 대해 최댓값을 구하면 된다. 안털게 된다면 이전 값을, 털게 된다면 전전 값에 현재값을 더하면 된다.

• a[i] = max(a[i-1], a[i-2] + now)

import sys

def solution(n, k):
    result = [0] * n
    result[0] = k[0]
    result[1] = max(k[0], k[1])
    for i in range(2, n):
        # 지금 털 것인지, 안 털고 이전 것을 그대로 사용할 것인지
        # 아래와 같이 작성하는 방법에 익숙해지자
        result[i] = max(result[i-2] + k[i], result[i-1])
    return result[n-1]

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    K = list(map(int, sys.stdin.readline().rstrip().split()))
    print(solution(N, K))

바닥 공사

---

해당 문제는 DP기초 예제 문제로 타일링 문제 유형이라고 한다.

이 문제도 다른 DP문제와 다르지 않게 점화식을 도출해 낼 수 있어야 한다.

• a[i] = a[i-1] * 2a[i-2]

왼쪽부터 타일을 채운다고 가정했을때, 세번째, 즉 3x2 지점 부터 일반화를 시킬 수 있다. 바로 이전까지 타일을 채운 상황에서 1x2 타일을 세로로 넣는 경우, 전전 칸 까지 타일을 채운 상황에서 2x2타일 하나를 넣거나, 2x1 타일 두 개를 가로로 채워서 넣는 경우 총 2가지 이다. 이를 점화식으로 세우면 위와 같다. 해당 과정이 복잡할 뿐 그 뒤로 코드 구현은 아래와 같이 쉽다.

import sys

def solution(n):
    # 입력의 최댓값 만큼 메모리 할당
    table = [0] * 1001

    table[0] = 1
    table[1] = 3
    for i in range(2, n):
        table[i] = (table[i-1] + 2*table[i-2]) % 796796
    return table[n-1]

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    print(solution(N))

효율적인 화폐 구성

---

해당 문제는 앞서 풀었던 그리디와 비슷하지만 화폐 가치가 배수로 이루어져있지 않아서 그리디는 아니다. 따라서 탐색을 해야 하는데, 중복 부분 문제가 발생한다. → DP

그렇다면 이 문제를 어떻게 점화식을 도출할 수 있을까

• a[i] = min(a[i], a[i-v] + v)

위에서 a는 DP테이블, v는 화폐 가치. 즉, v가 2일 경우, 2원을 포함하지 않은 이전 결과와 현재값의 비교를 통해 최적의 값을 구할 수 있다. 아래 코드는 바텀-업 방식을 사용한 코드이다.

import sys

def solution(n, m, values):
    table = [10001] * (m + 1)
    table[0] = 0
    for v in values:
        for i in range(v, m + 1):
            if table[i - v] != 10001:
                table[i] = min(table[i], table[i-v] + v)
    print(table)
    if table[m] == 10001:
        return -1
    return table[m]

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    Values = list()
    for _ in range(N):
        Values.append(int(sys.stdin.readline().rstrip()))
    print(solution(N, M, Values))