🔗 Problem Linkhttps://www.acmicpc.net/problem/2294❔Thinkingn개 종류의 동전을 활용해서, k원을 만드는 최소한의 동전 개수를 반환한다. k원을 만들 수 없다면 -1을 반환한다.1💻Solution1. DP를 활용한 풀이import sysinput = sys.stdin.readlinen, k = map(int, input().split())coins = []for _ in range(n): coins.append(int(input().rstrip()))coins.sort()answer = [float('inf') for _ in range(k+1)]answer[0] = 0for i in range(1, k+1): for coin in coins: ..

🔗 Problem Linkhttps://www.acmicpc.net/problem/2573❔Thinking2차원 배열에 빙산의 높이가 주어질 때, 일년마다 상하좌우에 있는 0의 개수만큼 높이가 줄어든다한 덩어리의 빙산이 두개 이상의 덩어리가 되는 최소한의 년수를 반환한다.상하좌우로 붙어 있어야 한 덩어리에 속한다. (즉, 대각선을 포함되지 않는다.)💻Solutionimport sysfrom collections import dequeinput = sys.stdin.readlineN, M = map(int, input().split())board = [list(map(int, input().split())) for _ in range(N)]total_ice = sum(cell > 0 for row in..

🔗 Problem Link 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net ❔Thinking 트리는 한 노드에서 다른 노드까지 가는 경로가 유일하다. 한 노드에서 가장 먼 노드는, 트리의 지름의 한 양 지점 중 하나이다. 💻Solution import sys import heapq input = sys.stdin.readline V = int(input()) tree = [[] for _ in range(V+1)] for _ in range(V): tmp = list(map(int, input..

🔗 Problem Link 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net ❔Thinking 배추밭과 배추의 위치가 주어질 때, 배추를 보호하는 최소한의 배추흰지렁이 수를 반환한다. 배추흰지렁이는 인접한 모든 배추를 보호할 수 있다. 💻Solution import sys from collections import deque input = sys.stdin.readline dx = [-1,1,0,0] dy = [0,0,-1, 1] T = int(input()) for _ in range(T): M, N, K = map(in..

🔗 Problem Link 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net ❔Thinking NXN 시험관에 바이러스가 순서대로 상,하,좌,우로 퍼져나갈 때, S초 뒤에 X,Y에 존재하는 바이러스를 반환한다. 바이러스는 1~K까지 있고, 작은 순서대로 퍼져간다. 💻Solution import heapq import sys input = sys.stdin.readline dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] n, k = map(int, input().s..

🔗 Problem Link 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net ❔Thinking 도시의 개수, 도로의 개수, 출발 도시의 번호가 주어질 때, 최단 거리가 k인 도시를 모두 출력한다. 💻Solution 1. BFS를 활용한 풀이 from collections import deque import sys input = sys.stdin.readline n, m, k, x = map(int, input().split()) graph ..