https://www.acmicpc.net/problem/10713
공부 날짜 : 2023.02.03
정답 참조 여부 : X
철도별로 티켓 가격, ic카드 사용시 가격, ic카드 가격이 나온다.
여행 계획에 맞춰서 철도를 이용할 때 경비의 최소값을 구하는 문제이다.
누적합으로 많이 풀어본 유형이다.
계획에 맞춰서 각 철도별로 사용횟수를 구해야 하는데, 각 철도별 횟수를 구하려고하면 시간초과가 나기때문에 누적합으로 풀 수 있도록 각 철도에서 사용횟수의 변화를 기록했다.
ex) 1 > 4으로 가면 1번철도에서 +1, 4번에서 -1하면 1,2,3에서는 1로 이동을 하게된다.
변화를 기록한뒤 누적합으로 각 철도별로 실제 사용횟수를 구하면
티켓사용경비 vs IC카드 사용경비를 구할 수 있다. 2개를 비교해서 더 작은값을 결과에 더해주면 되는 문제이다.
각 철도가 1번 2번 3번으로 주어지는게 아니라, 1~2번 2~3번으로 주어지기 때문에 많이 헷갈렸다.
3 > 2로 갈 때 3번에 횟수를 더해주는 실수를 했다. 이런 사소한 실수만 없었어도 쉽게 풀었을거 같은데 특정 값이 아니라 사이에 있는 값을 비교하는건 항상 어렵게 느껴진다.
예전에도 2차원 배열에서 각 배열의 사이에 벽의 유무를 판단하는 문제들이 많이 어려웠다.
각 값의 사이를 판단하는내용에 익숙해질 필요가 있어보인다.
소스코드
import sys
input = sys.stdin.readline
#########################################
n, m = map(int, input().split())
# 여행중 들릴 계획
plan = list(map(int, input().split()))
# 각 철도의 가격표
cost = [list(map(int, input().split())) for _ in range(n-1)]
# 각 철도별 사용횟수를 누적합으로 구할수 있게 저장
# 철도의 숫자 최대값은 n이므로 크기는 n+1
count = [0 for _ in range(n+1)]
# 계획일정에 맞춰서 사용횟수 저장
# 단, 숫자가 낮아질경우 반대로 저장
# 3 > 1로 가는걸 1 > 3으로 가는것과 철도 사용횟수는 같다.
for i in range(m-1):
if plan[i] < plan[i+1]:
count[plan[i]] += 1
count[plan[i+1]] -= 1
else:
count[plan[i+1]] += 1
count[plan[i]] -= 1
sum_ = 0
answer = 0
# 누적합으로 각 철도별 실제 사용횟수를 구함
# 그다음 사용횟수에따라 ic카드 구매비용 vs 티켓사용비용을 비교해서 작은값 결과에 추가
for i in range(n - 1):
sum_ += count[i+1]
answer += min(cost[i][0] * sum_, cost[i][1] * sum_ + cost[i][2])
print(answer)