🔗 Problem Link 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net ❔Thinking 마을과 임의의 두 마을 사이의 거리가 주어질 때, 모든 마을을 연결하는 최소 비용의 가로등 설치 비용을 반환한다. 가로등은 두 마을 사이의 거리만큼의 비용이 든다. 💻Solution import heapq def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(pa..

🔗 Problem Link 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net ❔Thinking 상담에 걸리는 시간과 상담에 따른 이익이 주어질 때, N+1일 이후에 얻게되는 최대 이익을 반환한다. 💻Solution n = int(input()) dp = [0] * (n+1) table = [] max_price = 0 for i in range(1, n+1): t, p = map(int, input().split()) table.append([t,p]) for i in range(n-1, -1, -1): time = table[i][0] + i if time

🔗 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 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❔Thinking 주어진 문자열을 1개 이상의 일정한 단위로 잘라 압축한 문자열 중, 가장 짧은 문자열의 길이를 반환한다. 💻Solution def solution(s): INF = int(1e9) answer = INF n = len(s) for i in range(1, n+1): tmp = '' prev = s[:i] cnt = 1 for idx in range(i, n, i): now = s[idx:idx+i] if prev == now: cnt += 1 else: tmp +=..

🔗 Problem Link 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net ❔Thinking 정수로 이루어진 삼각형에서, 위에서 큰 수를 선택해 더해 내려와 얻게되는 가장 큰 수를 반환한다. 왼쪽 대각선 아래, 오른쪽 대각선 아래의 수만 선택하여 더할 수 있다. 💻Solution 1. 위에서 내려오는 방법 import copy n = int(input()) graph = [[]] for i in range(n): graph.append(list(map(int, input().split()))) dp = copy.deepcopy(graph) for i in range(1, n): f..

🔗 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 ..