본문 바로가기

분류 전체보기

(402)
[백준 14464번] 소가 길을 건너간 이유 4 (Python3) from heapq import * def solve(): result = 0; hq = []; i = -1 for c in ch: for i in range(i+1,N): s,e = cow[i] if s>c: i -= 1 break heappush(hq,(e,s)) while hq: e,s = heappop(hq) if c
[백준 1114번] 통나무 자르기 (Python3) from bisect import * def cutting(l): i = 0; MAX = 0 for _ in range(C): idx = bisect(cut,l+cut[i])-1 MAX,i = max(MAX,cut[idx]-cut[i]),idx return max(MAX,L-cut[i]),L-cut[i] L,K,C = map(int,input().split()) cut = [0]+sorted({*map(lambda x:L-int(x),input().split())}) l,c,M,x = 1
[백준 16467번] 병아리의 변신은 무죄 (Python3) mod = 10**8+7 def multiply(A,B): S = [[0]*K for i in range(K)] for i in range(K): for j in range(K): for k in range(K): S[i][j] += A[i][k]*B[k][j] S[i][j] %= mod return S def cal(A,n): if n==1: return A c = cal(A,n//2); c2 = multiply(c,c) return multiply(c2,A) if n%2 else c2 for _ in range(int(input())): K,N = map(int,input().split()); K += 1 matrix = [[0]*K for i in range(K)] matrix[0][0] += 1;..
[백준 19585번] 전설 (Python3) import sys input = sys.stdin.readline def check(word): now = colors for i in range(len(word)): if now.get(0) and word[i:] in names: return 1 if not now.get(word[i]): return now = now[word[i]] C,N = map(int,input().split()) colors = {} for _ in range(C): now = colors for c in input().strip(): if not now.get(c): now[c] = {} now = now[c] now[0] = 1 names = {input().strip() for i in range(N)} for _ ..
[백준 16952번] 체스판 여행 2 (Python3) from collections import * dy = [[1,-1,0,0],[1,-1,1,-1],[1,1,-1,-1,2,2,-2,-2]] dx = [[0,0,1,-1],[1,1,-1,-1],[2,-2,2,-2,1,-1,1,-1]] def start(): for i in range(N): for j in range(N): if board[i][j]==1: return i,j def BFS(): result = C = 1e5 visited = [[[[[(1e5,0)]*N*N for i in range(N)] for i in range(N)] for i in range(3)] for i in range(8)] dq = deque([(p,*S,1,0,-1,0) for p in range(3)]) while d..
[백준 16959번] 체스판 여행 1 (Python3) from collections import * dy = [[1,-1,0,0],[1,-1,1,-1],[1,1,-1,-1,2,2,-2,-2]] dx = [[0,0,1,-1],[1,1,-1,-1],[2,-2,2,-2,1,-1,1,-1]] def start(): for i in range(N): for j in range(N): if board[i][j]==1: return i,j def BFS(): visited = [[[[[0]*N*N for i in range(N)] for i in range(N)] for i in range(3)] for i in range(8)] dq = deque([(p,*S,1,0,-1) for p in range(3)]) while dq: p,y,x,n,cnt,d = dq.pop..
[백준 23578번] 비 오는 날 (Python3) from heapq import * N = int(input()) nums = [*map(int,input().split())] hq = sorted((3*nums[i],nums[i],2) for i in range(N)) S = sum(nums) for i in range(N-2): w,n,x = heappop(hq) S += w heappush(hq,((x*2+1)*n,n,x+1)) print(S if N!=1 else 0) 우선순위 큐를 이용해서 해결하였다. 처음에는 단순한 MST 문제라고 생각했다. 하지만 어떤 노드와 어떤 노드가 연결되는지가 전혀 중요하지 않고 각 노드가 연결된 개수만 고려해주면 되기 때문에 그리디하게 해결할 수 있다. 풀이를 설명하면, 1. 일단 모든 노드가 전부 한번씩 연결되..
[백준 10160번] 암호 (Python3) N,K = map(int,input().split()) DP = [1]*(N+1) for n in range(1,N+1): DP[n] = DP[n-1]*K if n>4: DP[n] -= DP[n-5]*2 if n>6: DP[n] += DP[n-7] DP[n] %= 10**9+9 print(DP[N]) DP로 해결하였다. 풀이를 설명하면, 1. 길이 n 일때 암호의 경우의 수를 나타내는 DP배열을 만든다. 2. 패턴을 고려하지 않을 때, DP[n] = DP[n-1]*K이다. (문자 하나 추가) 3. 이때 패턴이 존재하면 안되므로 DP[n]에서 DP[n-5]*2를 뺀다. (패턴의 길이가 5이므로) 4. 패턴 2개는 ABCBC,ABABC인데 이 둘은 ABABCBC로 겹칠 수 있으며, 겹치는 경우는 이 경우가 ..