파이썬으로 풀어보는 백준 2651번: 자동차경주대회

https://www.acmicpc.net/problem/2651

2651번: 자동차경주대회

 

내 풀이:

distance = list(map(int,input().split()))   # N+1개의 자료
time = list(map(int,input().split()))      # N+1개의 자료
 
queue = [[0,B,0,[]]]   # 시간, 갈수있는 거리, n번째 장소, 들른 주유소
 
result = []
 
if B >= sum(distance):
    print("0")
    print("0")
    exit()
while queue:
    a = queue.pop(0)
    if a[2] == N:
        if a[1] - distance[a[2]] >= 0:
            result.append(a[0])
            if a[0] == min(result):
                lst = a[3]
            continue
 
    if a[1] - distance[a[2]] >= 0:
        queue.append([a[0], a[1]-distance[a[2]], a[2]+1, a[3]])
        next = a[3][:]
        next.append(a[2]+1)
        queue.append([a[0] + time[a[2]], B, a[2]+1, next])
 
print(min(result))
print(len(lst))
print(" ".join([str(i) for i in lst])) 

Python3, 시간초과

BFS와 DP 중 DP를 먼저 고민해보았으나 방법이 떠오르지 않아 BFS 방법을 택하였다. 위 방법의 경우 모든 정비소에 대해 '정비한다'와 '정비하지 않는다' 2가지의 case에 대해 나아간다. 때문에 최대 2^n 개의 경우의 수가 발생한다.

 

distance = list(map(int,input().split()))   # N+1개의 자료
time = list(map(int,input().split()))      # N+1개의 자료
 
queue = [[B,0,[]]]   # 갈수있는 거리, n번째 장소, 들른 주유소
 
result = []
if B >= sum(distance):
    print("0")
    print("0")
    exit()
while queue:
    a = queue.pop(0)
    if a[1] == N:
        if a[0] - distance[a[1]] >= 0:
            t = 0
            for __ in a[2]:
                t += time[__-1]
            result.append(t)
            if t == min(result):
                lst = a[2]
            continue
 
    if a[0] - distance[a[1]] >= 0:
        queue.append([a[0]-distance[a[1]], a[1]+1, a[2]])
        next = a[2][:]
        next.append(a[1]+1)
        queue.append([B, a[1]+1, next])
 
print(min(result))
print(len(lst))
print(" ".join([str(i) for i in lst])) 

Python3, 시간초과

코드를 작성하고 보니 queue에 시간이 굳이 들어갈 필요가 없어서 시간은 마지막에 정비를 받은 정비소 리스트만을 확인하여 시간을 계산하게 하여 전체 시간을 감소시키려고 노력하였다. 그러나 마찬가지로 시간초과를 해결하진 못했다.

 

B = int(input())
N = int(input())
distance = list(map(int,input().split()))   # N+1개의 자료
time = list(map(int,input().split()))      # N+1개의 자료
 
queue = [[B,0,[]]]   # 갈수있는 거리, n번째 장소, 들른 주유소
 
result = []
if B >= sum(distance):
    print("0")
    print("0")
    print("")
    exit()
 
while queue:
    size = len(queue)
    test = []
    for i in range(size):
        a = queue.pop(0)
        if a[1] == N:
            if a[0] - distance[a[1]] >= 0:
                t = 0
                for __ in a[2]:
                    t += time[__-1]
                result.append(t)
                if t == min(result):
                    lst = a[2]
                continue
 
        if a[0] - distance[a[1]] >= 0:
            queue.append([a[0]-distance[a[1]], a[1]+1, a[2]])
            next = a[2][:]
            next.append(a[1]+1)
            test.append([B, a[1]+1, next])
 
    t_lst = []
    for j in test:
        t = 0
        for __ in j[2]:
            t += time[__ - 1]
            t_lst.append(t)
    if t_lst == []:
        break
    b = t_lst.index(min(t_lst))
    queue.append(test[b])
 
print(min(result))
print(len(lst))
print(" ".join([str(i) for i in lst]))

Python3, 런타임 에러

정비를 받은 정비소에 대해서 지금까지 소요된 시간을 비교하여 시간이 가장 짧은 경우만 queue에 추가하도록 코딩을 하였는데 샘플은 잘 돌아갔으나 제출 시 런타임 에러가 발생하였다.

 

B = int(input())
N = int(input())
dis_data = list(map(int,input().split()))
time = list(map(int,input().split()))
 
distance = [0] * (N+2)
for idx, i in enumerate(dis_data):
    distance[idx+1] = distance[idx] + i
 
time = [0] + time + [0]
min_time = [9999999] * (N+2)
min_time[0] = 0
cnt = [0] * (N+2)
place = [[] for _ in range(N+2)]
 
for i in range(1, N+2):
    for j in range(i-1, -1, -1):
        if distance[i] - distance[j] <= B and min_time[i] > min_time[j]+time[i]:
            min_time[i] = min_time[j] + time[i]
            cnt[i] = cnt[j] + 1
            place[i] = place[j] + [str(i)]
 
print(min_time[-1])
print(cnt[-1]-1)
print(" ".join([str(i) for i in place[-1][:-1]]))

Python3, 56ms

BFS에서 DP로 풀이방법을 바꿨다. 저장하는 값의 기준은 n번 째 정비소에 도착하여 정비를 받을 경우 가장 짧은 소요 시간, 그동안 정비를 받은 정비소 리스트이다.(위의 코딩에서는 정비를 받은 정비소 수를 리스트로 저장하였으나 사실 len()을 이용하면 굳이 만들 필요는 없을 것 같다.)