✅ 문제 풀이 - BOJ 그래프 이론
🎈 1916 최소비용 구하기
N개의 도시가 있고 한 도시에서 출발해 다른 도시에 도착하는 M개의 버스가 있다. a번째에서 b번째 도시까지 가는 최소 비용을 출력하는 문제
입력은 다음과 같다.
- 첫 줄에 도시 개수 n, 둘째 줄에 버스 개수 m이 주어지고 셋째 줄부터 m+2줄까지 버스 정보가 주어진다. 마지막으로 m+3번째 줄에 출발점의 도시 번호와 도착점의 도시번호가 주어질 때, 최소 비용을 구하는 문제
import sys
input = sys.stdin.readline
import heapq
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
distance = [1e9] * (n+1)
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
def dijkstra(x):
heap = []
distance[x] = 0
heapq.heappush(heap, (x, 0))
while heap:
node, cost = heapq.heappop(heap)
if distance[node] < cost:
continue
for next_node, next_cost in graph[node]:
total = cost + next_cost
if distance[next_node] > total:
distance[next_node] = total
heapq.heappush(heap, (next_node, total))
start, end = map(int, input().split())
dijkstra(start)
print(distance[end])< 풀이 과정 >
일반적인 다익스트라 구현 문제
- n, m, graph, distance(노드 방문 당 비용 저장)을 만든 후 단방향 그래프를 채워준다.
- dijkstra 함수로 heap 자료구조를 이용해 다음 방문 시 비용이 최소화 되면 distance에 저장되도록 구현한다.
- start, end 지점을 입력받아 다익스트라 함수에 start를 넣고 end지점 기준 distance를 출력하여 start -> end 로 이동 시 발생하는 최소 비용을 출력
✅ 문제 풀이 - BOJ Greedy Algorithm
🎈 11501 주식
첫 줄에 테스트케이스 수 T가 주어지고 각 테케 별로 첫 줄에는 날짜 수, 둘째줄에는 날짜 별 주가가 주어졌을 때 최대 이익을 구하는 문제
각 날짜 별 주식을 매매하는 과정은 다음과정 중 하나를 거친다.
- 주식 하나를 산다
- 원하는 만큼 가지고 있는 주식을 판다
- 아무것도 안한다
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n = int(input())
price = list(map(int, input().split()))
profit = 0
val = 0
for i in range(len(price)-1, -1, -1):
if price[i] > val:
val = price[i]
else:
profit += val - price[i]
print(profit)< 풀이 과정 >
주어진 입력값들을 모두 처리한 후, 최대 이익 profit, 주어진 주가 내 비교를 위한 val을 변수로 둔다.
그 이후 최대 이익을 비교하기 위해 for문으로 끝부터 확인하여 price와 val을 비교하여 val보다 더 price가 크면 비교 대상인 val을 price값으로 저장하고, val이 더 크다면 최대이익 계산을 해준다.
🎈 16435 스네이크버드
첫 줄에 과일 개수 n, 스네이크버드 초기 길이 L이 주어지고 두번째 줄에 과일의 높이들이 주어질때 스네이크버드의 최대 길이를 출력하는 문제
스네이크 버드는 과일을 하나 먹으면 길이가 1만큼 늘어나고 스네이크 버드는 자신 길이보다 작거나 같은 높이에 있는 과일만 먹을 수 있다.
import sys
input = sys.stdin.readline
n, l = map(int, input().split())
height = list(map(int, input().split()))
height.sort()
for h in height:
if h > l:
break
elif h <= l:
l += 1
print(l)< 풀이 과정 >
주어진 과일들의 높이와 스네이크버드의 현재 길이를 비교하기 쉽게 하기 위해 height 리스트를 오름차순 정렬해준다.
for문으로 앞에서부터, 과일 높이가 버드길이보다 길면 과일을 못먹기에 break해주고 아닌 경우 버드길이를 1씩 늘려준다.
🎈 1417 국회의원 선거
첫 줄에 후보수 n이 50이하의 자연수로 주어지고 n줄 만큼 각 기호 별 득표 수가 주어진다.
기호 1번이 당선되도록 하기 위해 매수해야 하는 최소 인원 수를 구하는 문제.
import sys
input = sys.stdin.readline
n = int(input())
num_one = int(input())
vote = []
for _ in range(n-1):
vote.append(int(input()))
vote.sort(reverse = True)
answer = 0
if n == 1:
print(0)
else:
while vote[0] >= num_one:
num_one += 1
vote[0] -= 1
answer += 1
vote.sort(reverse = True)
print(answer)< 풀이 과정 >
주어진 후보 별 득표 수에 대해 기호 1번은 고정상태이므로 이를 num_one으로 저장해준다.
그 이후 n-1 줄 만큼 각 후보 별 득표수를 vote리스트에 저장한 후 내림차순 정렬한다.
만일 총 후보 수가 1이면 0표이므로 이를 if 조건을 걸어주고, 아닌 경우 while 문으로 가장 많이 득표한 수 vs 기호 1번 득표 수로 비교하며 기호 1번이 득표수가 더 많아지면 while문을 벗어나도록 조건을 걸어 반복한다.
매 횟수 마다 vote 리스트를 내림차순 정렬하며 가장 득표수가 많은 후보를 변경하며 비교해준다.
🎈 1461 도서관
세준이와 옮겨야 하는 책 n권의 위치 모두 0이고, 책의 수 n권과 세준이가 한번에 옮길 수 있는 책 수 m이 주어지고 옮겨야 하는 책의 위치가 주어졌을 대 책을 모두 제자리에 두는데 움직여야 하는 거리의 최솟값을 구하는 문제
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
location = list(map(int, input().split()))
positive = []
negative = []
answer = []
for loc in location:
if loc > 0:
positive.append(loc)
else:
negative.append(abs(loc))
positive.sort(reverse = True)
negative.sort(reverse = True)
for i in range(len(positive)):
if i % m == 0:
answer.append(positive[i])
for i in range(len(negative)):
if i % m == 0:
answer.append(negative[i])
answer.sort()
dist = 0
for i in range(len(answer)):
dist += 2 * answer[i]
dist -= answer[-1]
print(dist)< 풀이 과정 >
핵심은 책을 모두 제자리에 놔둔 이후 다시 0으로 돌아올 필요가 없다는 부분이다.
위 조건이 핵심인 이유는 가장 먼 곳에 위치하는 책을 시작부터 찾아가지 않아도 됨을 의미한다.
또한 들고 이동하는 책의 수가 m으로 고정되어 있으므로 이동 횟수를 최소로 하기 위해선 가장 먼 곳부터 책들을 들고 이동하는 것이 이동 횟수를 최소화할 수 있다.
따라서 다음 과정을 거치며 최소 이동 횟수를 구한다.
- 주어진 책의 위치 location 리스트를 생성한 이후 음수와 양수를 구분해주고 각 리스트를 내림차순 정렬한다.
- 한 번 이동 시 들고 이동하는 책의 권 수가 m으로 고정되어 있으므로 각 인덱스를 m으로 나누었을 때 나머지가 0인 책의 위치만 answer리스트에 추가해준다.
- 최종적으로 구하고자 하는 거리는 answer 리스트에 저장된 책의 위치들 * 2에 가장 먼 곳만 1회 더해주면 된다. (다시 돌아올 필요가 없으므로 반드시 빼주어야 함)
