본문 바로가기

분류 전체보기

 (402)
[백준 8464번] Non-Squarefree Numbers (Python) def check(x): cnt = 0; sq = 0 q = [(1,-1,1)] while q: n,i,s = q.pop() for j in range(i+1,P): n1 = n*prime[j]**2 if n1>x: break cnt += x//n1*s sq |= int(not x%n1) q.append((n1,j,-s)) return cnt,sq prime = []; visited = [0]*200001 for i in range(2,200001): if not visited[i]: prime.append(i) if i
[백준 10802번] 369 게임 (Python) def solve(X): X = [*map(int,str(X))]; L = len(X) for l in range(L): if X[l] and not X[l]%3: X[l] -= 1; X[l+1:] = [8]*(L-l-1) cnt = R = 0 for l in range(L): x = int(X[l]) for i in range(x): if i and not i%3: continue for r in range(3): if (R+i+r)%3: cnt += DP[r][L-l-1] R += x; R %= 3 cnt %= mod return cnt+int(R!=0) def remain(): DP = [[0]*N for i in range(3)]; DP[0][0] = 1 for i in range(1,N): fo..
[백준 1557번] 제곱 ㄴㄴ (Python3) def check(x): cnt = 0; sq = 0 q = [(1,-1,1)] while q: n,i,s = q.pop() for j in range(i+1,P): n1 = n*prime[j]**2 if n1>x: break cnt += x//n1*s sq |= int(not x%n1) q.append((n1,j,-s)) return x-cnt,sq prime = []; visited = [0]*50001 for i in range(2,50001): if not visited[i]: prime.append(i) if i
[백준 1210번] 마피아 (Python3) import sys input = sys.stdin.readline from collections import * def BFS(): dq = deque([0]) level = [0]*K; level[0] = 1 lvadj = [[] for i in range(K)] while dq: now = dq.popleft() for next in adj[now]: if graph[now][next]: if not level[next]: level[next] = level[now]+1 dq.append(next) if level[next]==level[now]+1: lvadj[now].append(next) if level[K-1]: return lvadj def DFS(now,f): if now==K-1: re..
[백준 17353번] 하늘에서 떨어지는 1,2, ..., R-L+1개의 별 (Python3) import sys input = sys.stdin.readline def update(i,j,v,s,e,x): if i==s and j==e: seg[0][x] += v seg[1][x] += 1 return mid = (s+e)//2 if jmid: update(i,j,v,mid+1,e,x*2+1) else: update(i,mid,v,s,mid,x*2); update(mid+1,j,v+mid+1-i,mid+1,e,x*2+1) def SUM(i,s,e,x): global S S += seg[0][x]+seg[1][x]*(i-s) if s==e: return mid = (s+e)//2 if i
[백준 11495번] 격자 0 만들기 (Python3) from collections import * def BFS(): parent = [K]*K dq = deque([-1]) while dq: now = dq.popleft() for next in adj[now]: if parent[next]==K and graph[now][next]-flow[now][next]: parent[next] = now dq.append(next) if next==-2: return parent def solve(): F = 0 while parent:=BFS(): now = -2; f = 1000 while now+1: last = parent[now] f = min(f,graph[last][now]-flow[last][now]) now = last now = -2 whil..
[백준 2365번] 숫자판 만들기 (Python3) from collections import * def BFS(x): parent = [-1]*K dq = deque([0]) while dq: now = dq.popleft() for next in range(K): if (c:=graph[now][next])
[백준 12963번] 달리기 (Python3) import sys,collections def input(): return map(int,sys.stdin.readline().split()) def BFS(): dq = collections.deque([0]) parent = [-1]*N while dq: now = dq.popleft() for next in adj[now]: if graph[now][next]-flow[now][next] and parent[next] 3^0+3^1+3^2+ ... + 3^(i-1)인 점을 이용하지 않을까 생각한다. 오늘의 교훈) 그리디한 방법으로도 문제를 해결해보자

티스토리툴바