4831 전기버스

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

나의 풀이

• 아이디어
  • 충전기가 있는 곳에 도착하면
    • 연료를 다 쓸떄까지 다음 충전기가 있는 곳에 도착할 수 있는지 확인
      • 도착할 수 있다면 충전x
      • 도착할 수 없다면 충전
  • 중간에 연료가 다 떨어져서 목적지에 갈 수 없는 상황일 경우 설정

import sys
sys.stdin = open("input.txt")

T = int(input())

for tc in range(1, T+1):
    # N 번 정류장까지 이동
    # K : 한번 이동시 최대 이동할수 있는 정류장수
    # M : 충전지가 설치된 M개의 정류장 갯수
    # sta_arr : 충전지가 설치된 정류장 리스트
    # result : 충전한 위치 리스트
    K, N, M = map(int,input().split())
    sta_arr = list(map(int, input().split()))

    sta_arr.append(N) # 마지막 위치도 충전 위치로 취급시키기
    fuel = K # 현재 남은 연료
    result= []

    for i in range(1, N+1) :
        fuel -=1

        # 현재 위치에 충전기가 있으면
        if i in sta_arr :
            check = False

            # 연료 다 쓸 때까지 다음 충전기가 있는지 확인
            for j in range(i+1, i+1+fuel) :
                if j in sta_arr :
                    check = True
            # 충전기가 있으면
            if check :
                continue
            # 충전기가 없으면 충전하기
            else :
                result.append(i)
                fuel = K
        # 연료가 떨어져서 목적지까지 갈 수 없을 경우
        if fuel == 0 :
            result =[]
            break

    # 도착 위치에서 충전을 했으면 빼주기
    if N in result :
        result.remove(N)
    print("#{} {}".format(tc, len(result)))

내가 생각하지 못한 풀이

• 아이디어
  • 일단 최대 거리까지 점프
  • 그 위치에서 하나씩 뒤로 와보면서 충전기가 있는 곳을 찾음
  • 만약 충전기가 없이 시작위치로 돌아오게 되면 목적지에 도착하지 못한것

import sys
sys.stdin = open("input.txt")

T = int(input())

# 일단 최대로 가보고 (만약에 종점 이상이면 그냥 break)
# 그 위치부터 하나씩 빼면서 충전기를 만나는 위치로 이동
# 만약에 충전기가 없이 시작 위치로 돌아오게 된다면
# 0 으로 출력하기

for tc in range(1, T+1):
    # N 번 정류장까지 이동
    # K : 한번 이동시 최대 이동할수 있는 정류장수
    # M : 충전지가 설치된 M개의 정류장 갯수
    # sta_arr : 충전지가 설치된 정류장 리스트
    K, N, M = map(int, input().split())
    sta_arr = list(map(int, input().split()))

    point = 0 # 움직이기 전 위치
    move = 0 # 움직이고 나서 위치
    result = 0 # 몇번 충전했는지

    while point < N:

        for i in range(point+K, point, -1) :
            if i >= N or i in sta_arr:
                move = i
                break
        if move == point :
            result =0
            break
        else :
            result +=1
            point = move

    print("#{} {}".format(tc, max(0,result-1)))