https://www.acmicpc.net/problem/10282 코드from heapq import heappop, heappushimport sysinput = sys.stdin.readlinefor _ in range(int(input())): n, d, c = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(d): a, b, s = map(int, input().split()) heappush(graph[b], (s, a)) # Dijkstra dist = [int(1e9)] * (n+1) dist[c] = 0 hq = [(0, c)] while..
문제풀이
https://www.acmicpc.net/problem/4097 코드from sys import stdininput = stdin.readlinewhile True: n = int(input()) if n == 0: break p = [int(input()) for _ in range(n)] ans = 0 dp = [0]*n for i in range(n): dp[i] = max(dp[i-1]+p[i], p[i]) # 계속 이어나가기 vs 새로운 시작 print(max(dp)) dp[i]에는 i번째 원소까지 확인했을 때, 마지막 원소(i번째)가 포함된 부분 배열 중 가장 합이 큰 부분 배열의 합이 저장된다. 그러므로 dp[i]에는 계속 이..
https://www.acmicpc.net/problem/1456 코드from math import sqrta, b = map(int, input().split())# 에라토스테네스의 체is_prime = [True]*(int(sqrt(b))+1)is_prime[1] = Falsefor i in range(2, int(sqrt(b))+1): if is_prime[i]: for j in range(i*2, int(sqrt(b))+1, i): is_prime[j] = False# 2~int(sqrt(b)) 사이의 소수들의 제곱수 중 a~b 사이에 존재하는 수의 개수 구하기ans = 0for i in range(2, int(sqrt(b))+1): if is_prime..
https://www.acmicpc.net/problem/6118 코드from collections import dequen, m = map(int, input().split())graph = [[] for _ in range(n+1)]for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a)# BFSq = deque([1])dist = [int(1e9)]*(n+1)dist[1] = 0ans = [-1, -1, -1]while q: now = q.popleft() for nx in graph[now]: if dist[nx] > dist[now]+1: ..
https://www.acmicpc.net/problem/2628 코드n, m = map(int, input().split())row, col = [0, m], [0, n]for _ in range(int(input())): num, line = map(int, input().split()) if num == 0: # 가로 row.append(line) else: # 세로 col.append(line)def longest(arr): # arr에 저장된 선분 간의 길이 중 가장 긴 것 리턴 arr.sort() res = 0 for i in range(1, len(arr)): if arr[i]-arr[i-1] >..
