본문 바로가기

분류 전체보기

(402)
[백준 2718번] 타일 채우기 (Python3) def DFS(n,now): if n == N-1: if 0 in graph[now]: DP[n][now] = 1 return for next in graph[now]: if not DP[n+1][next]: DFS(n+1,next) DP[n][now] += DP[n+1][next] for _ in range(int(input())): N = int(input()) DP = [[0]*16 for i in range(N)] graph = {0:{0,3,9,12,15},3:{0,12},6:{9},9:{0,6},12:{0,3},15:{0}} DFS(0,0) print(DP[0][0]) 비트마스킹을 이용한 DP로 구현하였다. 타일의 상태를 비트로 두고, 직접 손으로 그려서 해결하였다... 쉽게 말하면 현재 줄을..
[백준 15791번] 세진이의 미팅 (Python3) mod = 1000000007 N,K = map(int,input().split()) def cal(x,n): if n == 1: return x cal2 = cal(x,n//2) if n%2: return cal2*cal2*x %mod else: return cal2*cal2 %mod numer = denom = 1 for i in range(1,K+1): numer = numer*(N+1-i) %mod denom = denom*(i) %mod print(numer*cal(denom,mod-2)%mod) = [백준 11401번] 이항 계수 3 (Python3) (tistory.com)
[백준 3117번] Youtube (Python3) import sys,math input = sys.stdin.readline N,K,M = map(int,input().split()) student = [*map(int,input().split())] sparse = [[0]+[*map(int,input().split())]]+[[0]*(K+1) for i in range(30)] for i in range(1,31): for k in range(1,K+1): sparse[i][k] = sparse[i-1][sparse[i-1][k]] for i in range(31): if (1
[백준 16991번] 외판원 순회 3 (Python3) import sys,math input = sys.stdin.readline INF = 10**9 N = int(input()) co = [[*map(int,input().split())] for i in range(N)] graph = [[0]*N for i in range(N)] for i in range(N-1): x1,y1 = co[i] for j in range(i,N): x2,y2 = co[j] graph[i][j]=graph[j][i]=math.sqrt((x1-x2)**2+(y1-y2)**2) DP = [[-1]*N for i in range(1
[백준 1035번] 조각 움직이기 (Python3) import collections,itertools,copy dy = [1,-1,0,0] dx = [0,0,1,-1] def BFS(n,board): y,x = piece[n] board[y][x] = 0 dq = collections.deque([(y,x,0)]) visited = [[0]*5 for i in range(5)] arr = [] distance = 25 while dq: y,x,d = dq.popleft() if visited[y][x] or d>distance: continue visited[y][x] = 1 for i in range(4): y1,x1 = y+dy[i],x+dx[i] if 5>y1>=0 and 5>x1>=0: if board[y1][x1]==P[0] and not bo..
[백준 2536번] 버스 갈아타기 (Python3) import sys,collections input = sys.stdin.readline def cross(i,j): x1,y1,x2,y2,x3,y3,x4,y4 = *line[i],*line[j] return max(x1,x2)>=min(x3,x4) and max(x3,x4)>=min(x1,x2) and max(y1,y2)>=min(y3,y4) and max(y3,y4)>=min(y1,y2) M,N = map(int,input().split()) K = int(input()) line = [[*map(int,input().split())][1:] for i in range(K)] sx,sy,dx,dy = map(int,input().split()) line += [[sx,sy,sx,sy],[dx,dy,d..
[백준 2104번] 부분배열 고르기 (Python3) N,data = int(input()),[*map(int,input().split())]+[0] presum = [0] for i in range(N): presum.append(presum[-1]+data[i]) stack,result = [],0 for i in range(N+1): h = data[i] j = i while stack and stack[-1][0]>=h: h1,j = stack.pop() result = max(result,(presum[i]-presum[j])*h1) stack.append((h,j)) print(result) 히스토그램 [백준 6549번] 히스토그램에서 가장 큰 직사각형 (Python3) (tistory.com) 문제의 변형문제이다. 히스토그램은 (구간의 높이의 ..
[백준 1994번] 등차수열 (Python3) import sys,collections input = sys.stdin.readline N = int(input()) nums = [int(input()) for i in range(N)] result = collections.Counter(nums).most_common(n=1)[0][1] nums = sorted({*nums}) N = len(nums) Index = {nums[i]:i for i in range(N)} visited = [[0]*N for i in range(N)] for i in range(N-result): for j in range(i+1,N): if visited[i][j]: continue diff,l = nums[j]-nums[i],2 while Index.get(num..