SWEA 5208 전기버스2

URL

태그

브루트포스 알고리즘

백트래킹

문제 설명

•

정류장마다 교체 가능한 충전지를 이용해 최소한의 교체 횟수로 목적지까지 도달하는 경우의 수를 구하는 문제

◦

단, 출발지에서의 배터리 장착은 교환횟수에서 제외한다.

예제 입력/출력

•

입력1

Plain Text
복사

•

출력1

#1 1
#2 2
#3 5
Plain Text
복사

제약 조건

•

1≤T≤501 ≤ T ≤ 501≤T≤50

•

3≤N≤1003 ≤ N ≤ 1003≤N≤100

◦

0<Mi<N0 < M_i < N0<Mi​<N

문제 풀이

풀이1 브루트 포스 - 상한 O(N2)O(N^2)O(N2)

풀이 코드

MAX_NUM = int(1e9)

def dfs(idx, cnt):
    global N, stations, ans

    # Base Case
    if idx >= N - 1:
        ans = min(ans, cnt)
        return

    # 현재 교체 횟수가 이미 최솟값을 넘는 경우 가지치기
    if cnt >= ans:
        return

    # 현재 정류장에서 배터리를 교환하고 갈 수 있는 모든 경우의 수 탐색
    for i in range(1, stations[idx] + 1):
        dfs(idx + i, cnt + 1)

T = int(input())
for tc in range(1, T + 1):
    inputs = list(map(int, input().split()))
    N, stations = inputs[0], inputs[1:]

    ans = MAX_NUM
    dfs(0, -1)  # 1번 정류장에서 시작, 초기 교환 횟수 0

    print(f"#{tc} {ans}")
Python
복사