HTD

www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net import sys input = sys.stdin.readline def getIsPrimeNumberList(N): isPrimeNumberList = [True]*(N+1) isPrimeNumberList[1] = False for i in range(2, int(N**(1/2))+1): if isPrimeNumberList[i]: j = 2 while i*j

www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net import sys input = sys.stdin.readline N = int(input()) nums = [0]*10001 for _ in range(N): nums[int(input())] += 1 for i in range(10001): for j in range(nums[i]): sys.stdout.write(str(i)+"\n") 메모리 제한이 8MB인데, 10,000,000개의 숫자를 저장할 수는 없다.(이를 위해..

www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net import sys input = sys.stdin.readline T = int(input()) for _ in range(T): x1, y1, r1, x2, y2, r2 = map(int, input().split()) distance = ((x1-x2)**2+(y1-y2)**2)**(1/2) if x1 == x2 and y1 == y2: if r1 == r2: print(-1) else: print(0) else: if distance < r1+r2: big..

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net import sys import heapq input = sys.stdin.readline def bfs(start): global minWeights minWeights[start] = 0 heap = [] heapq.heappush(heap, (0, start)) while heap: curWeight, curNode = heapq.heappop(heap) for adjacentN..

def checkIsHansu(num): strNum = str(num) if len(strNum) >= 3: lastDiff = int(strNum[1]) - int(strNum[0]) for i in range(1, len(strNum)-1): if int(strNum[i+1]) - int(strNum[i]) != lastDiff: return False lastDiff = int(strNum[i+1]) - int(strNum[i]) return True hansuCount = 0 X = int(input()) for i in range(1, X+1): if checkIsHansu(i): hansuCount += 1 print(hansuCount) checkIsHansu()만 알면 된다. 숫자를 st..

www.acmicpc.net/problem/3020 import sys input = sys.stdin.readline N, H = map(int, input().split()) bottomObstacles = [0]*H topObstacles = [0]*H for i in range(N//2): o1, o2 = int(input()), int(input()) bottomObstacles[o1-1] += 1 topObstacles[o2-1] += 1 bottomPrefixSum = [0]*(H+1) topPrefixSum = [0]*(H+1) for i in range(H-1, -1, -1): bottomPrefixSum[i] = bottomPrefixSum[i+1] + bottomObstacles[i]..

www.acmicpc.net/problem/12904 S = list(input()) T = list(input()) lenS = len(S) while lenS T로 bfs를 이용해서 풀고자 하였는데, 아무리 시간 복잡도를 줄여도 소용이 없었다. 실은, 특정 문자열을 얻기 위한 방법이 오로지 하나였다. 그렇지 않은 줄 알고 많은 경우를 고려하려고 하였던 것이다. 풀이법은 간단하다. T의 마지막 문자에 따라서, A만 없애거나, B를 없애고 뒤집거나, 둘 중 하나의 연산을 해주고, T가 결국 S의 길이와 같게 되면 비교를..

www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net import sys input = sys.stdin.readline def getMaxDifferenceBetweenAdjacent(nums): nums.sort() maxDifference = max(abs(nums[0]-nums[1]), abs(nums[-1]-nums[-2])) for i in range(N-2): maxDifference = max(maxDifference, abs(nums[i]-num..

www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net import sys N, M = map(int, input().split()) graph = [[] for _ in range(N+1)] degree = [0 for _ in range(N+1)] for _ in range(M): inputL, inputR = map(int, input().split()) degree[inputR] += 1 graph[inputL].append(..

www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net import sys input = sys.stdin.readline N, M = map(int, input().split()) memories = [0] + list(map(int, input().split())) costs = [0] + list(map(int, input().split())) costSum = sum(costs) dp = [[0]*(costSum+1) for _ in range(N+1)] minCo..