HTD

https://www.acmicpc.net/problem/11049 import sys input = sys.stdin.readline if __name__ == '__main__': N = int(input()) nums = list(map(int, input().split())) for _ in range(N-1): _, c = map(int, input().split()) nums.append(c) # DP dp = [[0]*N for _ in range(N)] for d in range(N): for i in range(N - d): j = i + d if i == j: continue dp[i][j] = float('inf') for k in range(i, j): dp[i][j] = min(d..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net import sys sys.setrecursionlimit(300000) input = sys.stdin.readline def search(node): stack.append(node) visitInfo[node] = curSearchStart next = nums[node] nextVisitInfo = visitInfo[next] # 이번 탐색 때 방문한 경우 if nextVisitInfo == c..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net import sys import copy input = sys.stdin.readline dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def getCyclePositions(): airCleanerTopX = -1 airCleanerBottomX = -1 for i in range(R): if fineDusts[i][0] == -1: airCleanerTopX = i ai..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net import sys import itertools input = sys.stdin.readline dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def getMinChickenDistance(): minChickenDistance = float('inf') # 치킨집 위치 & 치킨집 -> 집까지 거리 저장 chickenPositions = [] for i..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys import itertools input = sys.stdin.readline if __name__ == '__main__': N, M = map(int, input().split()) nums = map(int, input().split()) for cur in sorted(list(set(itertools.permutations(nums, M)))): print(*cur)..

https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys import itertools input = sys.stdin.readline if __name__ == '__main__': N, M = map(int, input().split()) nums = sorted(set(input().split()), key=lambda x: int(x)) for cur in itertools.combinations_with_replaceme..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net import sys import heapq input = sys.stdin.readline def getPossibleItemCount(start): dp = [float('inf')]*(n+1) dp[start] = 0 todo = [(0, start)] while todo: curDist, curNode = heapq.heappop(todo) if curDist > dp[curNode]: conti..

https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net import sys import math input = sys.stdin.readline X = 1000000007 def getExpectedValue(n, s): return s * getSquaredNumber(n, X-2) % X def getSquaredNumber(num, exp): if exp == 1: return num if exp % 2 == 0: half = getSquaredNumber(num, exp//2) return hal..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net import sys input = sys.stdin.readline def getMinTimeAndCaseCount(N, K): if N >= K: return N-K, 1 curTime = 0 todo = [N] minTimes = [float('inf')]*100001 minTimes[N] = 0 while todo: print(todo) nextTodo ..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net import sys import heapq input = sys.stdin.readline def getMinCostAndPath(start, end): dp = [float('inf') for _ in range(n+1)] todo = [(0, start, [start])] while todo: curCost, curNode, curPath = heapq.heap..