Algorithm475 [파이썬] 백준 4386 : 별자리 만들기 (골드3) [파이썬] 백준 4386 : 별자리 만들기 (골드3)백준 4386 : 별자리 만들기 (골드3)풀이방향성 생각MST코드N = int(input())arr = [list(map(float,input().split())) for _ in range(N)]G = []for i in range(N-1): ax,ay = arr[i] for j in range(i+1,N): bx,by = arr[j] dist = ((ax-bx)**2+(ay-by)**2)**0.5 G.append((dist,i,j))G.sort()P = [i for i in range(N)]def find(x): if x != P[x]: P[x] = find(P[x]) retur.. 2025. 5. 14. [파이썬] 백준 14923 : 미로 탈출 (골드3) [파이썬] 백준 14923 : 미로 탈출 (골드3)[https://www.acmicpc.net/problem/1012](백준 14923 : 미로 탈출)풀이방향성 생각벽부수고 이동하기랑 똑같은 문제.visit 배열에 부순 횟수를 추가해서 3차원으로 풀이한다.코드from collections import dequeimport sysinput = sys.stdin.readlineinside = lambda x,y: 0코멘트. 2025. 5. 13. [파이썬] 백준 25195 : Yes or yes (골드4) [파이썬] 백준 25195 : Yes or yes (골드4)https://www.acmicpc.net/problem/25195풀이방향성 생각팬을 만나기 전 상태를 1, 만난 후 상태를 2라고 하면 1부터 전부 탐색했을 때 도착지점에 하나라도 도달할 수 있으면 성공이다.1만 먼저 탐색하기 위해서 다익스트라 사용.종료 조건 잘 생각하기.코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().strip()INF = float('inf')N,M = map(int,input().split())G = [[] for _ in range(N+1)]for _ in range(M): a,b = map(int,input().split()) G[a].. 2025. 5. 12. [파이썬] 백준 2225 : 합분해 (골드5) [파이썬] 백준 2225 : 합분해 (골드5)백준 2225 : 합분해 (골드5)풀이방향성 생각숫자 N을 만드는데 K개의 숫자를 쓰는 형태.숫자 N-X를 만드는데 K-1개의 숫자를 쓰는 부분 구조를 가지고 있다.DP를 통해서 계산 최적화시키기.$O(N*M)$이 굉장히 작은 경우라 바텀업이 빠르지만 탑다운으로 풀이.$dp[remain][number]$의 형태로 dp 배열을 작성한다.타 언어의 경우, 오버플로우의 위험 때문에 매 result에서 MOD 연산을 해줘야 할 수도 있는데 파이썬이라서 마지막 한 번만 MOD를 해주면 된다.코드N,K = map(int,input().split())MOD = 10**9dp = [[-1]*(N+1) for _ in range(K+1)]def dfs(x,cnt): # .. 2025. 5. 11. 이전 1 2 3 4 5 ··· 119 다음
