[SWEQ] 4831. 전기버스 - Python

https://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인 경우의 예이다.

 

< ❓ 생각 >

현재위치가 도착지점에 도착할 때까지 반복

  현재위치에서  최대 갈 수 있는 거리 계산해서 거기에 충전소가 있다면

  - 충전하고 충전횟수 증가

  없다면 뒤로 한 칸씩 이동하면서 충전소가 있는지 찾기.

  - 만약 충전소가 있다면 충전하고 충전 횟수 증가

  - 현재 위치까지 왔는데도 없다면 도착할 수 없는 것이므로 0 출력

 

  최대거리가 도착지점보다 멀거나 같을 경우 도착 -> 충전 횟수 출력

 

< 💻 코드 >

# T : 테스트 케이스 개수
T = int(input())
for tc in range(1,T+1):
    # K : 최대한 이동할 수 있는 정류장 수
    # N : 종점 정류장 번호
    # M : 충전기가 설치된 정류장 수
    K,N,M = map(int,input().split())
    arr = list(map(int,input().split()))
    cha = [0]*(N+1)
    for i in arr:
        cha[i] += 1
    # 현재 위치
    idx = 0
    # 충전 횟수
    cnt = 0

    # while 현재 위치가 아직 도착점이 아니면:
    while idx < N:
    # 충전소 찾기
    # 1. 갈 수 있는 최대 거리 계산
        if cha[idx+K]:
            idx = idx + K
            cnt += 1
    # 2. 최대거리 부터 뒤로 한 칸씩 가면서 충전소가 있는지 찾음
        else:
            for j in range(1,K):
      # 2-1 만약 충전소를 찾으면 충전하고 충전횟수증가
                if cha[idx+K-j]:
                    idx = idx + K -j
                    cnt += 1
                    break
      # 2-2 만약 현재위치까지 되돌아왔는데 충전소가 없으면, 충전하지 못함 횟수를 0으로 만들고 반복종료
            else:
                cnt = 0
                break

      # 2-3 만약 최대 거리가 도착점보다 멀거나 같으면, 반복종료
        if idx + K >=N:
            idx = N

    # 3. 충전횟수 출력하기
    print(f'#{tc} {cnt}')

 

< ❗ 느낀 점 >

오늘 공부한 알고리즘 중에 가장 어려웠다. 문제 이해는 했는데 코드 짜는게 막혀서 교수님께 질문한 문제ㅜ

주석으로 먼저 정리를 한 후에 하나하나 맞춰서 코드를 짰다.