3/22 Coding Test - BOJ

✅ 문제 풀이 - DP

🎈 1005 ACM Craft

첫 줄에 테스트케이스 수 T가 주어지고 첫 줄에는 건물 개수 n, 건설 순서 규칙 수 k가 주어지고 둘째줄에는 건물 당 건설에 걸리는 시간, 셋째줄부터 k+2번째 줄까지는 건설순서 x, y가 주어진다. 마지막 줄에 건설해야하는 건물 번호 w가 주어질 때, 건물 w를 건설하는데 드는 최소 시간을 출력하는 문제
건물은 번호 순서대로 지어야 하며 앞 건물이 완공된 이후 다음 건물을 지을 수 있다.

import sys
input = sys.stdin.readline
from collections import deque

t = int(input())
for _ in range(t):
	# 건물 수, 규칙 수
    n, k = map(int, input().split()) 
    # 건물 별 건설 시간, 범위 (0, n+1)
    time = [0] + list(map(int, input().split()))
    # 건설 순서 규칙 그래프 생성
    graph = [[] for _ in range(n+1)]
    # 방문 여부 확인
    visited = [0 for _ in range(n+1)
    # 건물 건설 시간 저장
    dp = [0 for _ in range(n+1)]
    for _ in range(k):
    	# 그래프 규칙 저장
        a, b = map(int, input().split())
        graph[a].append(b)
        # 방문 수 + 1
        visited[b] += 1
    queue = deque()
    for i in range(1, n+1):
    	# 방문 안한 곳에 한해 queue에 삽입하고 시작 건설시간 저장
        if not visited[i]:
            queue.append(i)
            dp[i] = time[i]
    # 큐 빌때까지 반복하며 꺼내고 다음 위치에 한해 방문 수 줄이고 max값 골라서 이동
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            visited[i] -= 1
            dp[i] = max(dp[x] + time[i], dp[i])
            if not visited[i]:
                queue.append(i)
    num = int(input())
    print(dp[num])

< 풀이 과정 >
위상정렬 알고리즘과 dp를 활용한 문제
위상정렬 알고리즘은 노드의 진입차수와 진출차수에 의해 순서가 정해지는 알고리즘이다.
큐에 진입차수(방문여부)가 0인 모든 노드를 큐에 넣고 건물 별 시간도 저장해준다. 그 이후 큐가 빌때까지 다음 과정을 반복한다

1. 큐에서 원소를 꺼내고 그래프 상 다음 위치들에 한해 방문 수를 1개 씩 제거하며 건설 시간을현재 건물까지의 건설 시간 + 다음 건물 건설 시간, 다음 건물까지의 건설 시간을 비교하여 max값을 갱신
2. 진입차수가 0인 노드에 한해 다시 큐에 넣는 작업을 반복

🎈 1890 점프

nXn 크기의 게임판이 있고 왼쪽 위에서 시작해 오른쪽 아래 칸으로 이동하는 문제
각 게임판에는 이동할 수 있는 거리가 주어지고 반드시 오른쪽이나 아래칸으로 이동하는 경우만 존재하고 최종적으로 문제 규칙에 맞게 이동할 수 있는 경로 개수를 출력하는 문제

import sys
input = sys.stdin.readline

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*n for _ in range(n)]
dp[0][0] = 1

for i in range(n):
    for j in range(n):
        if graph[i][j] != 0 and dp[i][j] != 0:
            if i + graph[i][j] < n:
                dp[i+graph[i][j]][j] += dp[i][j]
            if j + graph[i][j] < n:
                dp[i][j+graph[i][j]] += dp[i][j]
print(dp[-1][-1])

< 풀이 과정 >
주어진 n 과 그래프를 생성하고 경로 수를 저장하는 dp를 2차원 리스트로 만들어준다.
2중 for문을 돌며 오른쪽 아래만 0이므로 목적지에 도달하지 않은 범위에 한해

• 아래로 이동하는 i + graph[i][j] 수가 n보다 작을 경우에만 dp의 세로 값을 갱신해주고,
• 오른쪽으로 이동하는 j + graph[i][j] 수가 n보다 작을 경우에만 dp의 가로 값을 갱신해준다.

이런 방식으로 모든 행, 열을 반복하면 dp내 수들은 결국 이동하는 경로의 수를 담은 2차원 리스트가 되고 결과적으로 목적지인 오른쪽 아래 값 dp[-1][-1]을 출력한다.