https://www.acmicpc.net/problem/1680
1680번: 쓰레기 수거
쓰레기장에서 출발한 쓰레기차가 여러 지점들을 방문하며 쓰레기를 모으고 있다. 쓰레기차는 쓰레기장에서 가까운 지점부터 방문하며, 쓰레기를 모으다가 다음과 같은 경우에 쓰레기장으로 돌
www.acmicpc.net
문제에서 아래 3가지 경우에 쓰레기장으로 다시 돌아오게 된다.
특정 지점의 쓰레기를 실을 때는 한번에 모두 실어야하므로,
특정 지점에 도달했을 때 해당 지점의 쓰레기 양이 남은 용량보다 많다면 쓰레기장에 돌아갔다와야한다.
따라서, 쓰레기의 양과 남은 용량이 같아 쓰레기장으로 돌아오는 경우(case 1)와,
쓰레기의 양보다 남은 용량이 커서 다음 지점으로 진행하는 경우(case 2)로 나누어 풀이하였다.
T = int(input())
for _ in range(T):
W, N = map(int, input().split())
x = [0] * N
w = [0] * N
distance = 0 # 테스트 케이스 마다 distance와
W_capacity = W # 쓰레기 잔여용량을 초기화 해줘야 함
for i in range(N): # 각 지점의 거리와 쓰레기 양을 저장
x[i], w[i] = map(int, input().split())
i = 0 # i : 지점 인덱스
while i < N:
if W_capacity == w[i]: # 쓰레기 양이 용량에 도달한 경우, case 1
distance += 2 * x[i]
i += 1
W_capacity = W # case 2 이후 case 1이 발생한 경우 W_capacity 를 초기화 해줘야함
elif W_capacity > w[i]: # 쓰레기 양이 용량보다 작아 다음 지점으로 진행하는 경우, case 2
W_capacity -= w[i] # 용량이 다 차지 않을 경우 남은 용량 계산
i += 1 # 다음지점으로 진행
else:
distance += 2 * x[i] # 실을 수 있는 용량 보다 많은 경오 다시 돌아깄다 와야하므로,
W_capacity = W # 거리는 추가 되고, 잔여용량 초기화, 인덱스는 유지
if W_capacity < W: # 마지막 지점에서 쓰래기를 가득 채우지 않고 돌아온 경우
distance += 2 * x[N-1]
print(distance) # 모든 지점을 다 돈 뒤에 distance 출력
[백준/BOJ] #22352 항체 인식.python(파이썬) (0) | 2021.08.02 |
---|---|
[백준/BOJ] #22351 수학은 체육과목 입니다 3.python(파이썬) (0) | 2021.08.01 |
[백준/BOJ] #1463 1로 만들기.python(파이썬) (0) | 2021.07.30 |
[백준/BOJ] #1421 나무꾼 이다솜.python(파이썬) (0) | 2021.07.29 |
[백준/BOJ] #1431 시리얼 번호.python(파이썬) (0) | 2021.07.28 |