본문 바로가기

분류 전체보기

 (402)
[백준 12851번] 숨바꼭질 2 (Python3) import sys input = sys.stdin.readline from collections import deque INF = sys.maxsize N,K = map(int,input().split()) if N >= K: print(N-K) print(1) else: DP = [INF]*2*K count = [0]*2*K DP[N] = 0 count[N] = 1 dq = deque() dq.append(N) while dq: x = dq.popleft() if 2*x DP[x]+1: DP[2*x] = DP[x]+1 count[2*x] = 1 dq.append(2*x) elif DP[2*x] == DP[x]+1: count[2*x] += 1 dq.append(2*..
[백준 11054번] 가장 긴 바이토닉 부분 수열 (Python3) import sys input = sys.stdin.readline from collections import deque N = int(input()) seq = deque(map(int,input().split())) seq.appendleft(0) seq.append(0) DP1 = [0]*(N+1) DP2 = [0]*(N+1) for i in range(1,N+1): for j in range(i): if seq[i] > seq[j]: DP1[i] = max(DP1[i],DP1[j]+1) for i in range(1,N+1): for j in range(i): if seq[-1-i] > seq[-1-j]: DP2[-1-i] = max(DP2[-1-i],DP2[-1-j]+1) DP3 = [0]*N ..
[백준 10830번] 행렬 제곱 (Python3) 이전에 백준 1629번 곱셉 문제를 풀면서 분할정복을 이용한 거듭제곱 문제에 익숙해져 있었기에 간단한 문제라고 생각하고 코드를 금방 짰다. 그러나 생각보다 고려해야할 점이 많은 까다로운 문제였다. import sys input = sys.stdin.readline from collections import deque N,B = map(int,input().split()) A = [] for i in range(N): A.append(list(map(int,input().split()))) def calculate(A,B): if B == 1: return A if B%2 == 0: return multifly(calculate(A,B//2),calculate(A,B//2)) else: return mul..
[백준 9935번] 문자열 폭발 (Python3) 문자열이 최대 100만길이만큼 길 수 있기때문에 문자열 자체를 변경하는건 시간초과가 날 것이라 생각했다. 그래서 처음에 생각한 방법은 문자열 길이만큼의 체크리스트를 만들어 폭발 문자열에 해당하는 부분을 체크하고, 체크하지 않은 부분만 출력하는 방법이었다. 해당 코드는 다음과 같다. import sys input = sys.stdin.readline from collections import deque sys.setrecursionlimit(10**6) seq1 = input().strip() seq2 = input().strip() L1 = len(seq1) L2 = len(seq2) check = [0]*L1 def explode(start,now,cnt): if now+1 < L1: if seq1[n..
[백준 2448번] 별 찍기 - 11 (Python3) import sys input = sys.stdin.readline from collections import deque N = int(input()) star = [[" "]*N*2 for i in range(N)] def Triangle(y,x,n): if n == 3: star[y][x+2] = "*" star[y+1][x+1] = star[y+1][x+3] = "*" for i in range(5): star[y+2][x+i] = "*" else: Triangle(y,x+n//2,n//2) Triangle(y+n//2,x,n//2) Triangle(y+n//2,x+n,n//2) Triangle(0,0,N) for i in star: print("".join(i)) 처음에는 함수 자체에 print를..
[백준 1967번] 트리의 지름 (Python3) import sys input = sys.stdin.readline import heapq INF = sys.maxsize N = int(input()) graph = [[] for i in range(N+1)] for i in range(N-1): x1,x2,w = map(int,input().split()) graph[x1].append((x2,w)) graph[x2].append((x1,w)) hq = [] distance = [[-INF]*(N+1) for i in range(2)] def Dijkstra(node,distance): heapq.heappush(hq,(0,node)) while hq: w,now = heapq.heappop(hq) if distance[now] >= w: conti..
[백준 1043번] 거짓말 (Python3) import sys input = sys.stdin.readline from collections import deque N,M = map(int,input().split()) #사람수, 파티수 truelist = deque(list(map(int,input().split()))[1:]) party = [] for i in range(M): party.append(list(map(int,input().split()))[1:]) lielist = deque() countlist = [] def Party(partynum,count): truecount = liecount = 0 for i in party[partynum]: if i in truelist: truecount += 1 if i in lieli..
[백준 12865번] 평범한 배낭 (Python3) import sys input = sys.stdin.readline from collections import deque N,K = map(int,input().split()) WV = [] dq = deque() for i in range(N): WV.append(list(map(int,input().split()))) DP = [[0]*(K+1) for i in range(N+1)] for i in range(1,N+1): w,v = WV[i-1] for weight in range(1,K+1): if weight < w: DP[i][weight] = DP[i-1][weight] else: DP[i][weight] = max(DP[i-1][weight-w]+v,DP[i-1][weight]) print..

티스토리툴바