Hanbit the Developer

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

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net import sys input = sys.stdin.readline def printStar(N): curStar = [ " * ", " * * ", "***** "] curLen = 3 while curLen < N: for i in range(curLen): curStar.append(curStar[i]*2) curStar[i] = " "*curLen + curStar[i] + " "*curLen curLen *= 2 for s in curSta..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net import sys import heapq input = sys.stdin.readline def getMinTime(start, end): todo = [(start, 0)] dist = [float('inf')]*(N+1) dist[start] = 0 while todo: curNode, curDist = heapq.heappop(todo) if curDist..

https://www.acmicpc.net/problem/1504 import sys import heapq input = sys.stdin.readline def djikstra(start): dp = {i: float('inf') for i in range(1, N + 1)} dp[start] = 0 todo = [(start, 0)] while todo: curNode, curDist = heapq.heappop(todo) if dp[curNode] nextDist: dp[b] = nextDist heapq.heappush(todo, (b, nextDis..

https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net import sys input = sys.stdin.readline def getMinPossibleLength(string): length = len(string) pi = [0]*(length) j = 0 for i in range(1, length): while j > 0 and string[i] != string[j]: j = pi[j - 1] if string[i] == string[j]: j += 1 p..