one Book a Day

마지막 비교때 parent[v]==parent[u]로 썼다가 한참 틀렸다. 부모는 한칸위고 find가 루트를 찾는거라 find비교를 했어야했는데 두개의 차이에 대해 고민을 안해봤던 것 같아서 이런 문제가 생겼던 것같다. 오늘 확실히 알고간다. import sys input = sys.stdin.readline def union(a,b): #집합이 다를경우 합침 a=find(a) b=find(b) if a

매번 dp로 풀엇지만 브루트포스로도 풀린다고 한다. 처음부터 더해서 최댓값갱신. 다음 기회에는 풀어보는걸로, import sys input = sys.stdin.readline N = int(input()) T = [] P = [] dp = [] for i in range(N): a, b = map(int, input().split()) T.append(a) P.append(b) dp.append(b) dp.append(0) for i in range(N - 1, -1, -1): if i + T[i] > N: dp[i] = dp[i + 1] else: dp[i] = max(dp[i + 1], P[i] + dp[i + T[i]]) print(dp[0])

정석적인 다익스트라 문제 import sys input = sys.stdin.readline from heapq import heappop,heappush def dijkstra(start): min_dists[start] = 0 heap = [] heappush(heap,[0,start]) while heap: cur_dists, cur_node = heappop(heap) for next_node,next_dist in graph[cur_node]: if min_dists[next_node] > cur_dists + next_dist: min_dists[next_node] = cur_dists + next_dist heappush(heap,[min_dists[next_node],next_node]) ..

백준 선생님이 세그멘트트리 연습문제로 소개해주신 대표문제이다. segtree를 생성 후 구간탐색을 통해 구간합을 구한다. import sys input = sys.stdin.readline # 세그먼트 트리 생성 def init(node, start, end): # node가 leaf 노드인 경우 배열의 원소 값을 반환. if start == end : tree[node] = l[start] return tree[node] else : # 재귀함수를 이용하여 왼쪽 자식과 오른쪽 자식 트리를 만들고 합을 저장. tree[node] = init(node*2, start, (start+end)//2) + init(node*2+1, (start+end)//2+1, end) return tree[node] # 구..

이분탐색으로 종료시간을 구하고 역산해서 N직전까지 계산 후 하나씩더해주며 답을 찾는다. import sys input = sys.stdin.readline def isPossible(mid): cnt=0 for i in range(M): cnt += mid//amusement[i] + 1 if cnt >=N: return True return False # N명의 아이들 한줄 # M개의 1인승 놀이기구 # 운행시간 지나면 탑승하고 있던 아이 내리고 줄 맨앞에 있던 아이가 빈 놀이기구로 들어감. # 동시에 비어있으면 제일 앞에있는 놀이기구. N,M=map(int,input().split()) amusement = list(map(int,input().split())) start=0 end = 6e10 an..

브루트포스로 풀이 가능하다. import sys input = sys.stdin.readline # 브루트포스. # ord()로 가장 낮은 idx찾으려 했는데 맨앞이랑 맨끝때매 경우의수 너무 갈림. s = input().rstrip() l = len(s) answer = [] for i in range(l-2): for j in range(i+1, l-1): for k in range(j+1, l): new_s = s[:j][::-1] + s[j:k][::-1] + s[k:][::-1] answer.append(new_s) answer.sort() print(answer[0])

먼가 세그트리를 쓸수있을 것 같았으나 그냥 dp문제ㅋㅋ import sys input = sys.stdin.readline # 소 N마리 N,Q = map(int,input().split()) A = list(map(int,input().split())) dp = [0]*N # 미리계산. for i in range(N): dp[i] = A[i]*A[i-1]*A[i-2]*A[i-3] Qs = list(map(int,input().split())) # 미리계산 ex_sum = sum(dp) for idx in Qs: for i in range(4): new_idx = (idx-1+i)%N dp[new_idx] = -dp[new_idx] ex_sum+=2*dp[new_idx] print(ex_sum)

기본적인 플로이드 워셜 + 경로추적에 대한 알고리즘 일정지점 i부터 도착지까지 가는 모든 경로를 추적,출력 import sys input = sys.stdin.readline n=int(input()) m=int(input()) cities = [[float('inf') for _ in range(n+1)] for _ in range(n+1)] pre_node = [[0 for _ in range(n+1)] for _ in range(n+1)] for i in range(1,n+1): cities[i][i] = 0 for _ in range(m): a,b,c = map(int,input().split()) cities[a][b] = min(cities[a][b],c) # 이전노드 저장. pre_node[..

1차시 DFS 시간초과 import sys input = sys.stdin.readline def DFS(depth,start,sum_t): if depth==3: if arr[start]==sum_t: return True return for pre_num in arr[:start]: if DFS(depth+1,start,sum_t+pre_num): return True N = int(input()) arr = list(map(int,input().split())) # 앞에있는 수 3개의 합. DFS(중복가능) depth 3까지. cnt=0 for i in range(1,N): if DFS(0,i,0): cnt+=1 print(cnt) 2차시 누적합 메모리초과 import sys input = sys...

전형적인 0-1 냅색. dp로 풀었습니다. import sys input = sys.stdin.readline N,K = map(int,input().split()) dp =[[0]*(N+1) for _ in range(K+1)] times=[] grades=[] for _ in range(K): I,T = map(int,input().split()) times.append(T) grades.append(I) for class_no in range(1,K+1): for now_time in range(1,N+1): if times[class_no-1] > now_time: dp[class_no][now_time] = dp[class_no-1][now_time] else: # 지금시간에서 추가하는 과목의 ..