Algorithm475 [파이썬] 백준 1967 : 트리의 지름 (골드4) [파이썬] 백준 1967 : 트리의 지름 (골드4)https://www.acmicpc.net/problem/1967풀이방향성 생각모르면 노드마다 $N^2$로 돌리겠지만, BFS 두 번으로 해결이 가능하다.루트노드인 1번 노드에서 BFS를 돌리고, 가장 먼 지점에서 다시 한 번 BFS전체코드from collections import dequeimport sysinput = lambda : sys.stdin.readline().rstrip()N = int(input())G = [[] for _ in range(N+1)]for _ in range(N-1): a,b,cost = map(int,input().split()) G[a].append((b,cost)) G[b].append((a,cost.. 2024. 8. 1. [파이썬] 백준 9465 : 스티커 (실버1) [파이썬] 백준 9465 : 스티커 (실버1)https://www.acmicpc.net/problem/9465풀이방향성 생각상태를 나누는 기준은 줄 선택 / 이전에 스티커를 선택했는지 -> 2*2로 총 4가지이다.이전에 스티커를 선택한 경우 : 스티커를 선택하지 않은 경우 2가지 + 스티커를 선택한 경우 (반대 줄에서)이전에 스티커를 선택하지 않은 경우 : 스티커를 선택하지 않은 경우 2가지 + 스티커를 선택한 경우 2가지전체코드import sysinput = lambda : sys.stdin.readline().rstrip()def dp(N,arr): V = [[[0]*N for _ in range(2)] for _ in range(2)] V[1][1][0] = arr[1][0] V[1.. 2024. 8. 1. [파이썬] 백준 14938 : 서강그라운드 (골드 4) [파이썬] 백준 14938 : 서강그라운드 (골드 4)https://www.acmicpc.net/problem/14938풀이방향성 생각다익스트라 기본문제입력에서 노드 번호가 1번부터라서 이 부분만 맞춰주면 된다.다익에서 최소비용을 기록하고 그 비용이 주어진 범위 내에 있으면 아이템을 획득한다.모든 노드에 대해 다익을 돌리고 최대 아이템을 출력한다.전체코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()N,M,R = map(int,input().split())items = [0] + list(map(int,input().split()))G = [[] for _ in range(N+1)]for _ in range(R): .. 2024. 7. 31. [파이썬] 백준 29792 : 규칙적인 보스돌이 (골드5) [파이썬] 백준 29792 : 규칙적인 보스돌이 (골드5)https://www.acmicpc.net/problem/29792풀이방향성 생각딱 보면, 캐릭(가방)으로 최대의 값을 구하는 문제원래는 냅색으로 캐릭당 2중 for문, 총 3중 for문으로 풀 수 있다.$2^{13}K$라서 각 캐릭터로 BFS를 돌려도 충분히 가능한 문제전체코드from collections import dequeN,C,B = map(int,input().split())dmgs = [int(input()) for _ in range(N)]dmgs.sort(reverse=True)boss = [tuple(map(int,input().split())) for _ in range(B)]def bfs(dmg): V = [0]*(B+1.. 2024. 6. 22. 이전 1 ··· 41 42 43 44 45 46 47 ··· 119 다음