[2022 하계 모각코] 팀 "한 명 어디갔노" 5회차 - 계획 및 결과

목표
알고리즘 실력 향상을 위해 백준에서 출제하는 문제들을 풀어본다.

사용 언어
Python

일정
5회차: 8/3 14:00 ~ 17:00
목표 : 백준 DP 알고리즘 관련 3 - 4 문제 풀기

1. 백준 1005번
   

Code

import sys
from collections import deque

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

for _ in range(test):
    N, K = map(int, sys.stdin.readline().split())
    time = [0] + list(map(int, sys.stdin.readline().split()))   # 건물 건설 시간
    rule = [[] for _ in range(N + 1)]       # 건물 건설 규칙
    degree = [0 for _ in range(N + 1)]      # 진입 차수
    store = [0 for _ in range(N + 1)]       # 건물까지 걸리는 시간

    for _ in range(K):
        first, second = map (int, sys.stdin.readline().split())
        rule[first].append(second)
        degree[second] += 1

    q = deque()
    for i in range(1, N + 1):
        if degree[i] == 0:
            q.append(i)
            store[i] = time[i]

    while q:
        temp = q. popleft()
        for i in rule[temp]:
            degree[i] -= 1
            store[i] = max(store[temp] + time[i], store[i])
            if degree[i] == 0:
                q.append(i)

    ans = int(sys.stdin.readline())
    print(store[ans])

Result

2. 백준 2133번
   
   Code

n = int(input())
dp = [0 for i in range(31)]
dp[2] = 3
for i in range(4, 31, 2):
    dp[i] = dp[2] * dp[i - 2]
    for j in range(4, i, 2):
        dp[i] += 2 * dp[i - j]
    dp[i] += 2
print(dp[n])

Result

3. 백준 9251번
   
   Code

import sys

str1 = sys.stdin.readline().strip().upper()
str2 = sys.stdin.readline().strip().upper()
len1 = len(str1)
len2 = len(str2)
matrix = [[0] * (len2 + 1) for _ in range(len1 + 1)]

for i in range(1, len1 + 1):
    for j in range(1, len2 + 1):
        if str1[i - 1] == str2[j - 1]:
            matrix[i][j] = matrix[i - 1][j - 1] + 1
        else:
            matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1])

print(matrix[-1][-1])

Result