one Book a Day

처음 진입시 area[r][c]=2.. ctrl+z누르다 없어져서 한참틀렸다. import sys input =sys.stdin.readline from collections import deque def BFS(r,c,d): queue =deque() queue.append([r,c,d]) cnt=1 # 현재 위치를 청소한다. areas[r][c]=2 while queue: x,y,dir = queue.popleft() for n_dir in ((dir-1)%4,(dir-2)%4,(dir-3)%4,dir): # 현재위치에서 왼쪽부터 차례대로 인접한 칸을 탐색한다. nx=x+dx[n_dir] # 왼쪽에 청소할공간 없다면 다시 회전 ny=y+dy[n_dir] if not areas[nx][ny]: # 청소..

절차대로 구현하는 구현문제이다. 이런게 난이도 책정은 낮게되어이쓴데 실제로 좀 그림그리는게 필요해서 체감상 어려웠다 앞으로 구현문제 많이 풀어봐야겟다는 생각을 했다 import sys input = sys.stdin.readline from collections import deque N, K = map(int, input().split()) conveier = deque() conveier.extend(list(map(int, input().split()))) robot = deque() robot.extend([0]*N) K_cnt = conveier.count(0) ans=0 while K_cnt

마지막 비교때 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[..