Algorithm475 [파이썬] 백준 2479 : 경로찾기 (골드4) [파이썬] 백준 2479 : 경로찾기 (골드4)https://www.acmicpc.net/problem/2479풀이방향성 생각binary로 들어오는 데이터들을 정수형으로 변환한다.key index 정수 변환에 필요한 두 딕셔너리를 만든다.들어오는 bit 수가 1000개여서 전부 관리 가능하다.bit 연산을 통해서 입력 정수에 대해서 그래프를 만들어준다.BFS를 통해서 탐색하기단수 T/F 연산이 아니라 역추적이 필요하기 때문에 어디서 왔는지 기록목적지에 도달했으면 역추적, 아니면 -1 출력전체코드from collections import deque ,defaultdict as ddN,K = map(int,input().split())# key index bitnum_bin = {i:int(input().. 2024. 11. 16. [파이썬] 백준 1660 : 캡틴 이다솜 (골드5) [파이썬] 백준 1660 : 캡틴 이다솜 (골드5)https://www.acmicpc.net/problem/1660풀이방향성 생각사면체 만드는데 필요한 블럭 단위를 미리 만들어놓는다i개를 사용해서 만들 때, 블럭단위에 있는 t개 + dp[i-t]가 최소값인 경우 갱신전체코드N = int(input())dp = [1e9]*(N+1)tetra = [(n*(n+1)*(n+2))//6 for n in range(1,121) if (n*(n+1)*(n+2))//6 t: dp[i] = min(dp[i],dp[i-t]+1) else: breakprint(dp[N])코멘트python으로 잘 안돌아감$O(100N)$이라 안터질줄 알았는데 터져서 pypy로 풀이 2024. 11. 15. [파이썬] 백준 1240 : 노드 사이의 거리 (골드5) [파이썬] 백준 1240 : 노드 사이의 거리 (골드5)https://www.acmicpc.net/problem/1240풀이방향성 생각입력이 작아서 $N^2$로도 풀리는 기본 문제노드마다 BFS를 돌려서 거리를 구한다.큐에 노드와 거리를 같이 전달해서 V를 boolean으로 설정하거나, visit에 거리를 저장해서 이전 노드에서 불러온다.전체코드from collections import deque# node X에서 BFS를 돌려서 얻은 거리 리스트 반환def bfs(x: int) -> list: V = [-1]*(N+1) V[x] = 0 Q = deque([x]) while Q: x = Q.popleft() for nx,cost in G[x]: .. 2024. 11. 15. [파이썬] 백준 1083 : 소트 (골드4) [파이썬] 백준 1083 : 소트 (골드4)https://www.acmicpc.net/problem/1083풀이방향성 생각각 자리수 마다 남은 횟수 S에 대해서 Swap 가능한 범위가 주어진다.Swap 범위 내에서 해당 자리보다 큰 값이 주어지면 Swap을 반복한다.$N=50$이라 swap만 제대로 구현하면 시간적으로 문제될 일은 없다.전체코드N = int(input())arr = list(map(int,input().split()))T = int(input())goal = sorted(arr,reverse=True)# 해당 인덱스 a에서 앞으로 한칸 swapdef swap(array: list, a: int)->list: array[a],array[a-1] = array[a-1],array[a] .. 2024. 11. 14. 이전 1 ··· 37 38 39 40 41 42 43 ··· 119 다음