양갱로그

참고 사이트 : https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/ bellman-Ford's algorithm keywords : 최단 경로, 음수 사이클, 그래프 개념 벨만-포드 알고리즘은 Shortest path를 구할 때 graph 내 모든 edge에 대해 edge relaxation을 수행한다. 모든 노드 개수 : |V|-1개 모든 edge에 대해 edge-relaxation을 |V|-1회 수행한다. 방법) 시작 노드 A를 제외한 모든 노드의 value를 inf로 초기화한다. 노드 B에서 노드 C로 가는 경우, edge cost가 2인 경우, B노드 값 + 간선(B,C) = inf이기 때문에 업데이트할 필..

처음에 행렬제곱이랑 똑같다고 생각해서 matrix multiply → scalar multiply로 바꿨는데 바로 return할 수 있는 조건들을 따지다 보니 굳이 matrix 경우처럼 식이 길어질 필요가 없었음. 곱하고자 하는 수가 홀수이면 A가 한번 더 곱해진다는 것을 주의해서 풀어야했음.

- 파이썬으로 하면 시간초과나서 못풀음 - pypy3도 시간초과남 - 1000%1000 = 0 나와야하는거 생각해야함 - ^을 *로 표현할 수 있다는 것을 생각해야 분할로 풀기 가능 - define 쓰기 귀찮아서 scanf_s썼더니 계속 컴파일 에러

이게 왜 분할정복 문제인지 잘 모르겠다.. 분할정복으로 푸는 솔루션을 찾아봐야할듯..

N, M = map(int, input().split(' ')) arr = list(map(int, input().split(' '))) low = 0 high = 2000000000*30 #가장 오래걸리는 경우 최대 인원이 최대 시간 놀이기구 타는 경우 c = 0 time = 0 # 마지막 친구가 언제 탔는지 시간 먼저 계산해야함 while low=N: #애들이 너무 많음 time = mid high = mid-1 else: #애들 늘려야함 low = mid+1 # 마지막 친구가 자기 시간에 탄 놀이기구 번호를 계산해야함 # 처음엔 다 탐 ch = M for i in range(M): ch += (time-1)//arr[i]# 마지막 친구가 탄 시간 직전 시간까지 해당 놀이기구에 탔던 사람 수 알 수 ..