[Today I Learn] 2022.08.09

TIL

• 인덱스를 정확하게 사용하는 것이 중요하다
• 정확하게 사용하기가 어렵다고 생각하면, 메모리 공간을 추가시켜서 활용하는 방법도 생각해보자

 

What I did

1. APS 수강
2. list 알고리즘 solving club 문제 풀이 (4/5 문제)

Memo

• 알고리즘 문제 풀면서 애먹었다
• 아래 코드는 결과적으로 모든 테스트 케이스를 통과하진 못한 알고리즘.. 다만 고생했던 걸 기억하고 싶어서 메모

T = int(input())

for t in range(T):
    K, N, M = map(int, input().split())
    arr = list(map(int, input().split()))

    fuel_arr = [0 for i in range(N)]
    road = [0 for i in range(N)]
    for i in arr:
        road[i-1] = -1
    dist = []
    for i in range(M-1):
        dist.append(arr[i+1] - arr[i])
    dist.append(N - arr[M - 1])

    fuel_arr[0] = K-1
    ans = 0
    g = -1
    for i in range(1, N):
        if i == N - 1: break

        fuel_arr[i] = fuel_arr[i-1] - 1
        if road[i] == -1:                   # 주유소를 지나갈 때
            g += 1                          # 주유소 위치 증가 (몇번째 주유소인지 파악)
            if fuel_arr[i] < dist[g]:       # 연료보다 가야할 거리가 더 면 경우
                if (N-1-i) == fuel_arr[i]:  # 연료가 0일 때, 도착지점에 도착 했을 경우
                    continue                # 이상 없음
                else:                       # 연료가 0인데 도착하지 않았을 경우
                    fuel_arr[i] = K         # 연료 충전
                    ans += 1

        if fuel_arr[i] == 0 and road[i] == 0:
            ans = 0
            break

    print(f"#{t+1} {ans}")