백준/골드8 2169번 로봇 조종하기 - Python, DP 출처 : https://www.acmicpc.net/problem/2169 코드 import sys# 입력 처리data = sys.stdin.read().splitlines()N, M = map(int, data.pop(0).split(" "))mars = [list(map(int, data.pop(0).split(" "))) for _ in range(N)]dp = [[[-float('inf')] * 3 for _ in range(M)] for _ in range(N)]# 첫 번째 행 초기화dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = mars[0][0]for y in range(1, M): dp[0][y][0] = dp[0][y][1] = dp[0][y][2] = d.. 2025. 4. 2. 동전 1 출처 : https://www.acmicpc.net/problem/2293 코드 import sys# 입력input_data = sys.stdin.read().splitlines()N, K = map(int, input_data[0].split())coins = list(map(int, input_data[1:]))# 테스트용# N, K = 3, 10# coins = [1, 2, 5]dp = [0] * (K + 1) # dp[i] = i원을 만들 수 있는 조합의 개수dp[0] = 1 # 0원을 만드는 경우는 아무 동전도 사용하지 않는 경우 1가지for coin in coins: for i in range(coin, K + 1): dp[i] += dp[i - coin] # 현재 금.. 2025. 2. 20. 택배 배송 5972번 - Python, 다익스트라(Dijkstra) 출처 : https://www.acmicpc.net/problem/5972 코드 import heapqdef dijkstra(graph, start): INF = float('inf') N = len(graph) distance = [INF] * N distance[start] = 0 pq = [] heapq.heappush(pq, (start, 0)) while pq: now, dist = heapq.heappop(pq) for neighbor, weight in graph[now]: cost = dist + weight if cost 풀이 최소 비용을 구하는 문제이기에 다익스트라를 사용했습니다. .. 2025. 2. 7. 음악프로그램(2623) - Python, 위상정렬 https://www.acmicpc.net/problem/2623 코드 from collections import deque# 입력N, M = map(int, input().split())graph = [[] for _ in range(N + 1)]indegree = [0] * (N + 1)# 그래프 그리기for i in range(1, M + 1): info = list(map(int, input().split())) num_singers = info[0] order = info[1:] for j in range(num_singers - 1): graph[order[j]].append(order[j + 1]) indegree[order[j + 1]] +.. 2025. 1. 24. 숫자고르기 - Python https://www.acmicpc.net/problem/2668 코드 def solution(N, graph): visited = [False] * (N + 1) result = [] def dfs(start): stack, path = [start], [] while stack: node = stack.pop() if visited[node]: # 싸이클 발견 if node in path: idx = path.index(node) result.extend(path[idx:]) return .. 2025. 1. 22. 피자판매 2632번 - Pyton, 부분합 https://www.acmicpc.net/problem/2632 코드 from collections import Counter# 피자에서 가능한 부분합을 구하는 함수def find_sums(pizza, target): n = len(pizza) sub_sums = Counter() for i in range(n): sub_sum = 0 for piece in pizza[i:] + pizza[:i]: # 원형 배열 순회 sub_sum += piece if sub_sum > target: break sub_sums[sub_sum] += 1 if sum(pizza) 풀이.. 2025. 1. 1. 이전 1 2 다음
