티스토리 뷰
728x90
문제
thinking
정류장별 배터리 용량을 리스트로 만든 후, 1번 정류장부터 돌면서 교환횟수를 구해 비교했다.
최소한의 교체횟수를 묻고 있으므로 이전횟차까지의 결과값보다 같거나 크면 return 시키도록 함수를 구성했다.
함수의 인자로 현재위치(i), 최대로 갈 수 있는 범위(max_i), 해당타임 교환횟수(cnt)를 두어 일단 갈 수 있는 만큼 최대로 가보면서 cnt 값을 비교했다.
+ 교환횟수처럼 계속 변하는 값을 함수의 인자로 두면 코드짜는게 더 쉽다. 굿 ! ! !
코드
def dfs(i, max_i, cnt): # 현재위치(인덱스), 최대로 갈 수 있는 범위, 해당타임 교환횟수
global res
if cnt >= res:
return
if max_i >= N:
res = min(cnt, res)
return
for j in range(max_i, i, -1):
dfs(j, j + M[j], cnt + 1)
T = int(input())
for tc in range(1, T+1):
tmp = list(map(int, input().split()))
N = tmp[0]
M = [0] + tmp[1:] # 정류장 별 배터리 용량(1~N-1)
res = 10000
dfs(1, 1+M[1], 0)
print("#{} {}".format(tc, res))
'algorithm > swea' 카테고리의 다른 글
[swea] 5209. 최소 생산 비용 / python 파이썬 (0) | 2021.05.05 |
---|---|
[swea] 5205. 퀵정렬 / python 파이썬 (0) | 2021.05.05 |
[swea] 5204. 베이비진 게임 / python 파이썬 (0) | 2021.04.15 |
[swea] 5202. 화물 도크 / python 파이썬 (0) | 2021.04.15 |
[swea] 5201. 컨테이너 운반 / python 파이썬 (0) | 2021.04.15 |
댓글
글 보관함
TAG
- 삼성기출
- git 미러링
- 20056 마법사 상어와 파이어볼
- 백준
- merge 에러
- 2018 카카오 공채
- 프로그래머스
- 파이썬
- react
- Python
- 21609 상어 중학교
- 삼성코테
- dfs
- 영어끝말잇기
- 보석쇼핑
- BFS
- swea
- 20057 마법사 상어와 토네이도
- dp
- 브루트포스
- 기지국설치
- 알고리즘
- 17406 배열돌리기4
- 2579 계단오르기
- merge에러
최근에 올라온 글
- Total
- Today
- Yesterday
최근에 달린 댓글