HTD

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..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net import sys input = sys.stdin.readline def getNSquaredMatrix(n): # Base Case if n == 1: return matrix # Recursive Case halfSquared = getNSquaredMatrix(n//2) if n % 2 == 0: return squareMatrix(halfSquared, halfSquared) else: return s..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net import sys sys.setrecursionlimit(100000) input = sys.stdin.readline def getPostorder(nums): length = len(nums) if length nums[0]: return getPostorder(nums[1:i]) + getPostorder(nums[i:]) + [nums[0]] return getPostorde..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net import sys input = sys.stdin.readline AIR, CHEESE = 0, 1 dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def getMinTime(): minTime = 0 while meltCheese(): minTime += 1 return minTime def meltCheese(): outerPositions = [(i, 0) ..