알고리즘문제-전기버스
전기버스 알고리즘
- SWEA 4831 - [파이썬 S/W 문제해결 기본 1일차] LIST1 - 전기버스
- 문제링크
- 문제의 저작권은 SW Expert Academy에 있습니다.
문제풀이 1 Brute-force search
모든 경우의 수를 모두 확인하여 가장 좋은 값을 확인
- 먼저 버스가 도착할 수 있는지 확인하고,
- 도착할 수 있을 경우 가장 적은 충전 횟수를 확인한다. (1과정에서 포함 가능하겠다)
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
# ///////////////////////////////////////////////////////////////////////////////////
[k, n, m] = [int(i) for i in input().split(' ')]
mm = [int(i) for i in input().split(' ')]
## Possiblity test
start = 0
arrive = False
for i in mm:
if start + k >= i:
start = i
else:
break
if start + k >= n:
arrive = True
break
if arrive == False:
print("#" + str(test_case) , 0)
continue
## Brute-force search
cnt_min = m
for i in range(pow(2,m)):
pos = 0
cnt = 0
for j in range(m):
if ( (1<<j) & i ):
if pos + k >= mm[j]:
pos = mm[j]
cnt += 1
if pos + k >= n and cnt_min > cnt:
cnt_min = cnt
print( "#"+str(test_case), cnt_min)
# ///////////////////////////////////////////////////////////////////////////////////
문제풀이 2
Brute-force search 를 통하여 정답은 잘 찾을 수 있겠지만, 시간제한에 걸렸다…
주어진 문제의 조건을 살펴보면,
한번 충전후에는 k 번만큼 이동할 수 있다. 충전 횟수가 최소가 되려면 이동할 수 있는 거리안에 있는 충전기 중 가장 멀리 있는 충전기에서 충전을 하면 될 것 같다.
- 이때, k 번 안에 충전기를 찾지 못하면 실패
- 목적지에 도달하기까지 충전 횟수가 정답이 될 것이다.
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
# ///////////////////////////////////////////////////////////////////////////////////
[k, n, m] = [int(i) for i in input().split(' ')]
mm = [int(i) for i in input().split(' ')]
mm = [int(i) for i in input().split(' ')]
nm = [0 for _ in range(n+1)]
for i in mm:
nm[i] += 1
cnt = 0
curpos = 0
endpos = k
while True:
kk = 0
for i in range(curpos+1, endpos+1):
if nm[i] == 1:
curpos = i
else:
kk+=1
if kk >= k:
cnt = 0
break
cnt += 1
endpos = curpos + k
if endpos >= n:
break
print("#"+str(test_case), cnt)
# ///////////////////////////////////////////////////////////////////////////////////
실행 결과 테스트를 통과 하였다!