본문 바로가기

분류 전체보기

 (402)
[백준 14476번] 최대공약수 하나 빼기 (Python3) import sys input = sys.stdin.readline from math import sqrt def check(x): cnt = 0 idx = 0 for i in range(N): if nums[i]%x: cnt += 1 idx = i if cnt > 1: return 2,0 return cnt,idx def divide(x,idx): for i in range(N): if i == idx: continue nums[i] //= x N = int(input()) data = [*map(int,input().split())] nums = data[:] nums.sort() MIN = nums[1] sq = int(sqrt(MIN)) sqsq = int(sqrt(sq)) prime = [] v..
[백준 1508번] 레이스 (Python3) import sys input = sys.stdin.readline from bisect import bisect_left def calmin(): MIN = N+1 for i in range(1,M): if MIN > location[where[i]]-location[where[i-1]]: MIN = location[where[i]]-location[where[i-1]] idx = i return idx,MIN def relocation(): global where idx,MIN = calmin() newwhere = where[:] for i in range(idx,M): new = bisect_left(location,location[newwhere[i-1]]+MIN+1) if new >= K: r..
[백준 1800번] 인터넷 설치 (Python3) import sys input = sys.stdin.readline from heapq import heappush,heappop INF=1e9 N,M,K = map(int,input().split()) graph = [[] for i in range(N)] for i in range(M): x,y,w = map(int,input().split()) graph[x-1].append((y-1,w)) graph[y-1].append((x-1,w)) DP = [[INF]*N for i in range(K+1)] hq = [] heappush(hq,(0,0)) while hq: w,now = heappop(hq) if DP[0][now]
[백준 1162번] 도로포장 (Python3) import sys input = sys.stdin.readline from heapq import heappush,heappop INF=sys.maxsize N,M,K = map(int,input().split()) graph = [[] for i in range(N)] for i in range(M): x,y,w = map(int,input().split()) graph[x-1].append((y-1,w)) graph[y-1].append((x-1,w)) DP = [[INF]*N for i in range(K+1)] hq = [] heappush(hq,(0,0)) while hq: w,now = heappop(hq) if DP[0][now]
[백준 12969번] ABC (Python3) def bubble(): for i in range(N-1): if S[i]>S[i+1]: S[i],S[i+1] = S[i+1],S[i] return return True def ABC(): for i in range(K): if bubble(): return -1 return "".join(S) N,K = map(int,input().split()) S = ["C"]*(N//3)+["B"]*((N-N//3)//2)+["A"]*(N-N//3-(N-N//3)//2) print(ABC()) 아이디어를 떠올리기 약간 어려웠던 문제. 버블 소트에 관한 문제를 풀었던 것이 아이디어를 떠올리는데 도움을 주었다. 알고리즘을 설명하면, 일단 순서쌍의 최대 갯수는 A,B,C가 N/3씩 순서대로 나열될 때이다. 예를 들어..
[백준 1071번] 소트 (Python3) import sys input = sys.stdin.readline N = int(input()) A = [*map(int,input().split())] A.sort() cntlist = {} for a in A: if cntlist.get(a): cntlist[a] += 1 else: cntlist[a] = 1 numlist = sorted(cntlist) N = len(numlist) seq = [] for i in range(N): n = numlist[i] if not cntlist[n]: continue if i == N-1: for _ in range(cntlist[n]): seq.append(n) break if numlist[i+1]==n+1: if i==N-2: for _ in rang..
[백준 1033번] 칵테일 (Python3) import sys input = sys.stdin.readline from collections import deque from math import gcd def cocktail(): for d in depth: for now in d: for next in child[now]: p,q = ratio[next] if value[now]*q == value[next]*p: continue if value[now]%p: value[0] *= p//gcd(value[now],p) return True value[next] = value[now]//p*q N = int(input()) graph = [[] for i in range(N)] for i in range(N-1): a,b,p,q = map(int..
[백준 13511번] 트리와 쿼리 2 (Python3) import sys input = sys.stdin.readline from collections import deque from math import log2 def findparent(x,d): for i in range(logd+1): if d&(1

티스토리툴바