[파이썬] 4831. 전기버스

swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

A도시는 전기버스를 운행하려고 한다. 전기버스는 한번 충전으로 이동할 수 있는 정류장 수가 정해져 있어서, 중간에 충전기가 설치된 정류장을 만들기로 했다.

버스는 0번에서 출발해 종점인 N번 정류장까지 이동하고, 한번 충전으로 최대한 이동할 수 있는 정류장 수 K가 정해져 있다.

충전기가 설치된 M개의 정류장 번호가 주어질 때, 최소한 몇 번의 충전을 해야 종점에 도착할 수 있는지 출력하는 프로그램을 만드시오.

만약 충전기 설치가 잘못되어 종점에 도착할 수 없는 경우는 0을 출력한다. 출발지에는 항상 충전기가 설치되어 있지만 충전횟수에는 포함하지 않는다.

[예시]

다음은 K = 3, N = 10, M = 5, 충전기가 설치된 정류장이 1, 3, 5, 7, 9인 경우의 예이다.

 

[입력]
 

첫 줄에 노선 수 T가 주어진다.  ( 1 ≤ T ≤ 50 )

각 노선별로 K, N, M이 주어지고, 다음줄에 M개의 정류장 번호가 주어진다. ( 1 ≤ K, N, M ≤ 100 )
 

[출력]

#과 노선번호, 빈칸에 이어 최소 충전횟수 또는 0을 출력한다.

 

입력	출력
3 3 10 5 1 3 5 7 9 3 10 5 1 3 7 8 9 5 20 5 4 7 9 14 17	#1 3 #2 0 #3 4

 

🎃 모르겠는 것

1. 반복문을 어떻게 짜지? 시작을 못하겠다.

 

👑 다른사람 풀이

 

T=int(input())
for test_case in range(1, T+1):
    K, N, M = map(int,input().split())    # K=최대이동횟수, N=정류장, M=충전기
    charge = list(map(int, input().split()))  # 충전기
    station_lst=[0]*(N+1)					# 정류장(출발점0 포함)
    
    for i in range(len(charge)):
        station_lst[charge[i]]+=1		# 정류장 station_lst에서 충전기가 있는 곳만 1로 초기화
        
    start=0		# start와 end는 이동거리
    end=K
    cnt=0    #충전횟수
    
    while True:
        zero=0
        for i in range(start+1, end+1):
            if station_lst[i] == 1: 		# 주유소에 도착하면
                start=i							# 시작점을 주요소가 있는 위치로 
            else:
                zero+=1
        if zero == K:				# 종점에 도착을 못해
            cnt=0
            break
            
        cnt+=1
        end=start+K
        
        if end >= N:		# 도착하면
            break
    print('#%s %d' %(test_case, cnt))

 

코드가 길뿐 쉽네;;

정류장 station_lst는 0부터 시작하므로 길이를 N+1만큼 해준다. 

for문으로 정류장 station_lst charge[i]인덱스에 1을 초기화한다.

while문내의 for문은 최대이동거리만큼 반복한다.

station_lst[i]가 1이면 주유소에 도착한 것이다. start를 이 위치로 초기화한다.

그렇지 않으면 zero를 1증가시킨다. zero가 K랑 같으면 충전기 설치가 잘못되어 종점에 도착할 수 없는 경우이다.

end는 start+k로 늘어난다.

end가 N보다 크거나 같으면 도착한것이므로 while문을 break한다.

 

import sys
sys.stdin = open("inputs/bus_input.txt")
def solution(K, N, stops):
    """
    :param K: 한번 충전시 갈 수 있는 정류장 수
    :param N: 종점까지 정류장 갯수
    :param stops: 충전기가 설치된 정류장 목록 (번호로 주어짐)
    :return: 최소한의 충전 횟수
    SW Expert Academy 4831. 전기 버스(d3) / 시간복잡도 : O(n) 예상
    """
    answer = prev = 0
    # answer는 최종 정답, prev는 현재 정거장과 다음 정거장의 거리를 계산하기 위해 사용
    status = K
    # status는 현재 충전 현황을 뜻함
    for i in range(len(stops) - 1):
        status -= stops[i] - prev
        # 그 다음 충전기가 있는 정류장까지 갔으므로 충전 현황을 계산
        if status < 0:
            return 0 # 만약 0보다 작다면 충전량으로 현재 정류소까지 갈 수 없으므로 0 반환
        if stops[i + 1] - stops[i] > status:	# 다음 정류장까지의 거리를 계산 후 status와 비교
            status = K
            answer += 1
        """
        핵심로직!
        우리의 관심사는 충전소가 있는 정류장마다 충전하는 것이 아니다!
        충전 횟수를 최소화해야하므로 그다음 현재 가지고 있는 충전량으로 그다음 충전소까지
        갈 수 있는지 계산하여 충전하도록 만듦
        """
        prev = stops[i] # 이전 정류소 갱신
    # for문에서 마지막 정류소를 계산하지 않았으므로 마지막 정류소까지 계산
    last = stops[-1]
    status -= last - prev
    if N - last > K:		# 도착할 수 없다
        return 0
    elif N - last > status:
        answer += 1
    return answer

def main():
    T = int(input())
    for test_case in range(T):
        K, N, M = map(int, input().split())
        stops = list(map(int, input().split()))
        print(f"#{test_case + 1} {solution(K, N, stops)}")

if __name__ == '__main__':
    main()

 

for문의 범위를 len(stops)-1로 해야 if stops[i+1]-stops[i]>status에서 index 에러가 안난다.

status는 충전소 stops[i]에서 이전 정거장 prev를 뺀 값을 뺀다. status를 연료로 생각하기.

status가 음수가 되면 0을 return한다.

현재 충전소와 그 다음 충전소의 거리를 계산하고 status와 비교한다. status가 더 작으면 충전이 필요하다. status는 K로 만땅 채우고 충전 횟수 answer이 1 증가한다.

한 번 충전 시 갈 수 있는 정류장 수 K보다 크면 return 0을 한다.

prev에 stops[i]를 넣어준다.

for문이 끝나면 마지막 충전소에 대해 계산한다.

마지막 충천소가 최대 이동거리 K보다 더 멀리 떨어져 있다면 return 0

그렇지 않고 정류장 거리 N-마지막 충전소 last가 연료 status보다 크면 충전횟수를 늘린다.

 

👠 느낀점

나도 2번 코드처럼 충전소의 거리만으로 계산하고 싶었는데,,ㅋㅋ

연료 status와 이전 충전소 prev가 있어야 했다.