Algorithm475 [파이썬, 자바] 백준 23848 : 등비수열의 합 (골드3) [파이썬, 자바] 백준 23848 : 등비수열의 합 (골드3)https://www.acmicpc.net/problem/23848풀이방향성 생각10^12 -> 최대 공비 10^6 -> O(N)으로 풀이항이 3개 이상이어서 r^3 = 10^12로 풀면 10^4까지 줄일 수 있다고 생각했는데, N**(1/3)까지 줄일 수 있다고 생각했는데 안되는듯? 항 개수가 부족해서 답이 안될거같았는데...구간합 구하기 -> 누적합 사용누적합의 길이가 가장 긴 2의 경우, 10^12 = 2^40이라 잡으면 누적합 리스트의 길이는 최대 약 40투포인터로 구간길이가 3 이상인 구간합이 N의 약수인 경우 찾기.구간합 * a(scaling factor?) = N이므로 N/a == N//a이면 조건 만족지금 보니까 나머지가 0이면 .. 2025. 2. 16. [파이썬, 자바] 백준 20158 : 사장님 달려가고 있습니다 (플레5) [파이썬, 자바] 백준 20158 : 사장님 달려가고 있습니다 (플레5)https://www.acmicpc.net/problem/20158풀이방향성 생각지문이 조금 애매하다. 테케 3번을 통해서 잘 이해해보자.현재 시간이 t이고 가속도가 a일 때, 가속도가 붙은 방향으로 a+1만큼 이동해야한다.도착 지점에서 진입이 막히는 경우는 nt부터이다.하지만, 도착지점까지 달려나갈 때 진입이 막히는 경우는 nt+1부터이다.state는 4가지로 구분한다. x,y,dire(방향),accel(가속도)같은 위치에 도착하더라도 어떤 방향이고, 어떤 가속도로 왔냐에 따라서 다음 노드로 가는데 영향을 준다.가속도는 최대 15까지 가능하다 (15 이상이면 한 방향으로 계속 달렸다는건데, 이 때 항상 맵 밖을 넘어가게 되어있다) .. 2025. 2. 13. [파이썬,자바] 프로그래머스 : 지게차와 크레인 (레벨2) [파이썬,자바] 프로그래머스 : 지게차와 크레인 (레벨2)프로그래머스 : 지게차와 크레인 (레벨2)풀이방향성 생각padding을 해줘서 테두리를 추가한 후, BFS로 외곽과 닿아있는 부분을 감지한다.각 query 실행 -> BFS를 통해서 boundary update. pythondef solution(storage, queries): inside = lambda x,y : 0 return boundary def bfs(): V = [[0]*W for _ in range(H)] V[0][0] = 1 Q = deque([(0,0)]) while Q: x,y = Q.popleft() for dx,dy in d.. 2025. 2. 11. [파이썬, 자바] 백준 1800 : 인터넷 설치 (골드1) [파이썬, 자바] 백준 1800 : 인터넷 설치 (골드1)https://www.acmicpc.net/problem/1800풀이방향성 생각DFS로 node N까지 경로 메모리에 저장한다든가, 탐색을 여러 번 진행하면 TLE 발생.limit원까지 지불할 수 있을 때 node N까지 도달할 수 있냐 없냐를 확인한다.금액 크기가 $10^6$이므로 이분탐색 20번 정도면 풀이가 가능하다.$O(20*NlogN)$이고 N이 크지 않아서 시간은 널널하게 풀이가 가능이분탐색은 가장 비싼 간선 limit 제한이 걸렸을 때 node N까지 진행이 가능한가를 확인하고, 다익스트라는 N번 노드까지 사용한 전선의 개수를 기록한다. 파이썬import heapq as hqimport sysinput = lambda : sys.std.. 2025. 2. 10. 이전 1 ··· 25 26 27 28 29 30 31 ··· 119 다음
