문제 설명
•
정류장마다 교체 가능한 충전지를 이용해 최소한의 교체 횟수로 목적지까지 도달하는 경우의 수를 구하는 문제
◦
단, 출발지에서의 배터리 장착은 교환횟수에서 제외한다.
예제 입력/출력
•
입력1
3
5 2 3 1 1
10 2 1 3 2 2 5 4 2 1
10 1 1 2 1 2 2 1 2 1
Plain Text
복사
•
출력1
#1 1
#2 2
#3 5
Plain Text
복사
제약 조건
•
•
◦
문제 풀이
풀이1 브루트 포스 - 상한
풀이 코드
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
복사