[SW Expert Academy] 전기버스 문제

삼성 SW 아카데미의 Learn의 Intermediate 코스의 첫 강의, List1의 문제 중 전기 버스 문제에 대한 코드이다.

문제링크

def move(list_charger, my_loc, max_move, index, max_point): #파라미터 : 충전가능정류장 리스트, 내 위치, 최대 이동 정류장 수, 충전 가능 정류장 번호, 종점
    num_charged = 0; #추가 충전 횟수
    check = 0 #업데이트 여부 체크       
    for i in range(len(list_charger)): 충전기가 있는 정류장 마다 반복
        if list_charger[index] - my_loc - max_move < 0: # 내 위치에서 최대로 갈 수 있는 정류장 까지의 경로 중 충전 가능 정류장이 있는 경우
            index = index+1 #다음 충전 가능 정류장으로!
            check = 1 #위치 업데이트 완료
            
            if index > len(list_charger) - 1: # 다음 충전 가능 정류장이 없는 경우
                return [list_charger[index-1], num_charged + 1, 0]
                
        elif list_charger[index] - my_loc - max_move == 0: #딱 다음 정류장까지 갈 수 있는 경우
            return [list_charger[index], num_charged+1, 1]
        else: #다음 충전소 까지는 못갈것 같다! 다시 이전 충전소로 가서 충전하자
            if check == 0: return [0, 0, -1] #이전 충전소가 없었다?? 종점 못가
            return [list_charger[index-1], num_charged+1, 1]

#return : my location, number of additional charge

def solution():
    temp = list(map(int, input().split())) # 입력받기 (이동가능한 최대 정류장, 종점까지의 정류장 수, 한번 충전으로 이동할 수 있는 최대 정류장 수)
    max_move = temp[0] # 한번 충전으로 갈 수 있는 최대 정류장 수
    num_station = temp[1] # 총 정류장 수
    num_charger = temp[2] # 충전 가능 정류장 수
    my_fuel = max_move

    list_charger = list(map(int, input().split())) # 충전 가능한 정류장 리스트를 받는다

    ans = 0 # 충전 횟수
    my_loc = 0; # 현재 있는 정류장 위치

    for i in range(100000): #무한루프
        if my_loc + max_move < num_station:  #아직 종점까지 안갔을 경우
            a = move(list_charger, my_loc, max_move, ans, num_station) #정류장 이동
        else: #종점까지 간 경우
            return ans # 충전횟수 반환 및 함수 종료
        my_loc = a[0] # 현재 정류장 위치 업데이트
        ans = ans + a[1] # 충전 횟수 증가
        if a[2] == -1:
            return 0
        if a[2] == 0: break
    return ans


aaa= solution()
print(aaa)

알고리즘의 동작 원리는 다음과 같다. 현재 위치에서 충전 가능한 정류장을 일단 방문해본다. 가장 가까운 충전가능 정류장을 가본 뒤 원래 위치에서 가진 연료로 갈 수 있는지 판단한다. 나올 수 있는 케이스는 다음과 같다.

1. 가고도 연료가 남는다.
2. 갔더니 연료가 딱 맞아떨어졌다.
3. 연료가 모자른다.

- CASE 1

연료가 남은 경우, 다음 충전 가능한 정류장도 방문해본다. 이후 위 케이스에 재적용해서 판단한다.

- CASE 2

연료가 딱 맞아 떨어진 경우, 해당 정류장에서 충전하고 과정을 반복한다.

- CASE 3

연료가 부족한 경우 이전 충전 가능한 정류장으로 가서 충전을 하고 과정을 반복한다.

이제 코드를 같이 보며 분석해보자

끝!