SWEA 13565 전기버스

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AYJ7KE5qKy8DFASv&contestProbId=AX7UKy7KaMwDFAVm&probBoxId=AYJ7KE5qKzADFASv&type=USER&problemBoxTitle=list1&problemBoxCnt=5 

SW Expert Academy

 

풀이방법

풀이 key point)

최소 횟수로 충전을 해서 끝까지 가려면

한번 갈때 배터리가 감당할 수 있는 최대 칸으로 가면 좋다.

즉, 지금칸+K번째칸부터 확인 후, 그 곳에 충전기가 없으면

지금칸+(K-1)번째칸... 이런식으로 확인하면 된다.

 

 

 

 

 

T = int(input())

for tc in range(1, T+1):
    K, N, M = map( int, input().split())
    stations = [0]* (N+K+1) #버스정류장 위치표시
    station_numbers = list(map(int, input().split()))
    #station에 위치표시
    for i in range(M):
        stations[station_numbers[i]] = 1

    current_station = 0 #지금 버스가 있는 위치
    charge_times = 0 #충전횟수
    flag =0

    while current_station <= N:
        battery = K
        for t in range(K, 0, -1):
            if stations[current_station+t] == 1:
                current_station += t
                charge_times += 1
                break
                #범위 안에 있으면 충전횟수+1, 지금 역 위치 바꾸기
            else:
                battery -= 1
                #아니면은 battery에서 1빼고 다시 for문 돌기
            if current_station >= N - K:
                #마지막까지 갈수 있는 station에 도달한경우
                flag = 1
                break
            elif battery == 0:
                #배터리가 떨어진 경우
                flag = 1
                #그동안 온거 초기화하고 0 입력
                charge_times = 0
                break
        if flag:
            break

    print(f'#{tc} {charge_times}')

flag를 잘 활용해서 while문을 빠져나오는 경우는 flag = 1으로 설정해주면 훨씬 더 쉽게 풀 수 있다.

이 경우에는 아예 목적지에 도달했을 때, 그리고 배터리가 방전되는 경우에 while문을 끝내야 한다.

배터리가 방전되어서 끝나는 경우는 charge_times를 꼭 초기화해주자.