[TIL_Carrotww] 109 - 23/04/25

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 백준 평범한 배낭

처음에 dfs로 일단 풀어봤다.
시간 초과가 나서 이거 dp 문제인가 싶어서 찾아봤다.
역시 내가 약한 dp문제... 검색해보니 스냅 뭐시기라고 하는데 그냥 dp 아닌가... 싶었다.

• 풀이

def solve():
    import sys

    N, K = map(int, sys.stdin.readline().split())
    dp = [[0]*(K+1) for _ in range(N+1)]
    thing_list = [[0, 0]]
    for _ in range(N):
        thing_list.append(list(map(int, sys.stdin.readline().split())))

    for i in range(1, N+1):
        for j in range(1, K+1):
            w = thing_list[i][0]
            v = thing_list[i][1]

            if j < w:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], v+dp[i-1][j-w])

    print(dp[N][K])

if __name__ == "__main__":
    solve()

dp 문제는 이해하면 쉽지만 그 전에는 뭔가... 싶다 솔직히 문제를 보고도 잘 생각이 나지 않는다.
처음에는 그리디인가? dfs 문제인가? 싶었다.
dp... 많이 풀어야겠다.

🔍 백준 돌멩이 제거

정답률 높아서 풀어본 플레 문제인데 왜 정답률이 높은지 알았다.
쉬워서가 아니라 아무도 못풀어서 그냥 답 붙여넣어서 정답률이 높은거다.
처음에 그리디로 생각했는데 가로 세로로어디부터 시작해야할지 그걸 모르겠어서 나도 검색을 해봤다.
그런데 이 문제를 풀기위해서는

• 최대 이분 매칭
• 최소 버텍스 커서
• 콰니그의 정리

위 세가지를 알아야 풀 수 있고 이해가 가능하다...
시간이 걸려서 이해를 하긴 했다. 막상 이해하면 이해는 되는데 응용 문제가 나오면 풀 수 있을까...?
코테에 이런 문제가 나올까? 싶기는 하다.

• 풀이

if __name__ == "__main__":
    import sys
    N, K = map(int, sys.stdin.readline().split())
    graph = {x:[] for x in range(1, N+1)}
    for _ in range(K):
        row, col = map(int, sys.stdin.readline().split())
        graph[row].append(col)

    matching = [False for _ in range(N+1)]

    def dfs(idx):
        if visited[idx]:
            return False
        visited[idx] = True

        for i in graph[idx]:
            idx_i = matching[i]
            if idx_i == False or dfs(idx_i) == True:
                matching[i] = idx
                return True
        return False

    result = 0
    for i in range(1, N+1):
        visited = [False for _ in range(N+1)]
        if dfs(i):
            result += 1

    print(result)