Tag: dynamic programming

INF = float('inf')

n = int(input())

total_sum = 0
select_idx = []
for _ in range(n):
    L = int(input())
    jewels = list(map(int, input().split()))

    cum_sum = [0] * (L + 1)
    for i in range(1, L + 1):
        cum_sum[i] += cum_sum[i - 1] + jewels[i - 1]
    
    max_sum = -INF
    max_start = 1
    max_end = L

    for k in range(L, 0, -1):
        is_max = False
        for i in range(0, L - k + 1):
            part_sum = cum_sum[k + i] - cum_sum[i]
            if max_sum > part_sum:
                continue
            # 최대값과 같고 이미 앞에서 그 값이 나온 경우
            elif max_sum == part_sum and is_max:
                continue

            max_sum = part_sum
            max_start = i + 1
            max_end = k + i
            is_max = True
    total_sum += max_sum
    select_idx.append((max_start, max_end))


print(total_sum)
for result in select_idx:
    print(*result)

1. (0, 0)에서 시작
2. 오른쪽(→), 아래(↓) 방향으로만 이동
3. 값이 1인 칸만 이동 가능
4. (M-1, N-1)에 도달하면 성공

from collections import deque

N, M = map(int, input().split())

space = [list(map(int, input().split())) for _ in range(M)]

dyx = ((1, 0), (0, 1))

q = deque([(0, 0)])
visited = set([(0, 0)])

is_possible = False

if N == 1 and M == 1:
    is_possible = True

while q:
    y, x = q.popleft()
    for dy, dx in dyx:
        ny, nx = y + dy, x + dx
        if not(0 <= ny < M and 0 <= nx < N):
            continue
        if space[ny][nx] == 0:
            continue
        if (ny, nx) in visited:
            continue
        if (ny, nx) == (M - 1, N - 1):
            is_possible = True
            break

        q.append((ny, nx))
        visited.add((ny, nx))
    else:
        continue
    break

# print(visited)
print('Yes' if is_possible else 'No')

import heapq
T = int(input())

for _ in range(T):
    K = int(input())

    res = 0
    files = list(map(int, input().split()))
    
    dp = [[0] * K for _ in range(K)]
    sum_list = [0] * (K + 1)

    # 누적합
    for i in range(K):
        sum_list[i + 1] = sum_list[i] + files[i]
    
    for i in range(1, K):
        for j in range(i, K):
            dp[j - i][j] = float('inf')
            for k in range(j - i, j):
                dp[j - i][j] = min(dp[j - i][j], dp[j - i][k] + dp[k + 1][j])
            dp[j - i][j] += sum_list[j + 1] - sum_list[j - i]
    
    print(dp[0][K - 1])

def max_subset_sum(arr):
    dp = [[0, 0] for _ in range(c + 1)]

    for num in arr:
        for j in range(c, num - 1, -1):
            if dp[j - num][0] + num > c:
                continue
            next_sq_value = dp[j - num][1] + num ** 2
            if next_sq_value > dp[j][1]:
                dp[j][0] = dp[j - num][0] + num
                dp[j][1] = next_sq_value
    _, max_sum = max(dp, key=lambda x: x[1])
    return max_sum

test_case = int(input())

for t in range(test_case):
    n, m, c = map(int, input().split())
    honey_map = [list(map(int, input().split())) for _ in range(n)]
    total_max = 0

    for fst_i in range(n):
        for fst_j in range(n - m + 1):

            fst_max = max_subset_sum(honey_map[fst_i][fst_j:fst_j + m])

            for snd_i in range(n):
                start = 0
                if snd_i == fst_i:
                    start = fst_j + m
                for snd_j in range(start, n - m + 1):
                    snd_max = max_subset_sum(honey_map[snd_i][snd_j:snd_j + m])

                    total_max = max(total_max, fst_max + snd_max)

    print(f"#{t + 1} {total_max}")

탐색 완료: 1, 2, 3

이렇게 목표 건물이 4번이 queue에 들어와 탐색을 마치면 4번 건물을 지었다는 것이므로 탐색을 멈추고 저장해두었던 시간을 출력하면 된다.

이 문제의 입력으로 주어지는 건물들로 만들어진 그래프는 항상 방향성을 가지며, 항상 모든 건물이 건축 가능하도록 주어진다고 했기 때문에 acyclic이다. 즉 이 문제의 그래프는 DAG(Directed Acyclic Graph)이다. DAG에서 어떤 노드로 들어오는 간선의 개수를 indegree라고 하는데 이 indegree의 개수에 따라 정렬하는 것을 위상 정렬(topologicla sort)이라고 한다.

따라서 우리가 위에서 필요 건물(indegree)에 따라 정렬하여 시간을 계산한 것은 위상 정렬을 이용한 알고리즘인 것이다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

def dp(b1, b2, n, m):
    global memo
    if b1 == n:
        return 1
    cnt = 0
    for i in range(b2 + 1, min(m, b2 + m - n + 1) + 1):
        if (b1 + 1, i) in memo:
            cnt += memo[(b1 + 1, i)]
        else:
            tmp = dp(b1 + 1, i, n, m)
            cnt += tmp
            memo[(b1 + 1, i)] = tmp
    return cnt

t = int(input())
for _ in range(t):
    memo = {}
    n, m = map(int, input().split())
    print(dp(0, 0, n, m))