ABC 338 D 실패

 

N개의 섬이 순서대로 연결되어 있다.

M개의 섬 투어 계획이 나왔을 때 최소 이동 횟수를 구하여라.

다만, 다리 하나는 끊어져야하고 선택할 수 있다.

# 실패한 코드
N, M = map(int, input().split())
X = list(map(int, input().split()))


def f(i, j, e):  # I to J
    global N
    if i > j:
        if e < j < i:
            return i - j
        elif j <= e < i:
            return N - i + j
        elif j < i <= e:
            return i - j
    else:
        if e < i < j:
            return j - i
        elif i <= e < j:
            return i + N - j
        elif i < j <= e:
            return j - i


ans = 1000000000000000
for e in range(N):  # i번째 다리가 닫힘
    m = 0
    for k in range(1, len(X)):
        m += f(X[k - 1], X[k], e)
    ans = min(ans, m)

print(ans)

브루트포스로 1번째 다리부터 N번째 다리가 끊어졌을 상황을 순회하며

f라는 함수로 투어의 각 섬으로 이동하는 거리를 구했다.

문제는

1. 브루트포스 전 시간계산을 하지 않았다.

2. 함수 f를 너무 대충 작성했다.

정도이다.

잘한점은

1. 다리가 끊어지지 않았을 때는 N번째 다리를 이용하거나 i - j로 바로 가거나 두가지 경우가 있지만

    다리가 끊어졌을 때는 경우의 수가 하나로 줄어든다는 것을 파악했다.

2. 어떤 자료구조(?)가 필요하다는 것을 파악했다.

해결은

1. 다리 e가 끊어졌다 했을 때 i == e거나 j == e일 때만 섬의 이동거리가 변화한다.

    따라서 투어의 거리를 다리가 변화할 때마다 구할 필요 없다.

    처음 합에서 변화시키는 방법으로 누적합의 아이디어와 비슷하다.

2. i > j인 경우

i, j = j, i

   를 통해 뒤집기만 하면 된다.

배울점은

1. range(1, M) 반복문과 i - 1, i 비교 대신 range(M - 1) 반복문 i, i + 1 비교 --취향차이일 수도 있다.

2. i > j 를 방지했다.

# 1, 2번
for i in range(M - 1):
    l, r = min(X[i], X[i + 1]), max(X[i], X[i + 1])

3. 아이디어 (누적합의 역이라 하자)

# 전체 코드/정답 코드
N, M = map(int, input().split())
X = list(map(int, input().split()))

d = [0] * (N + 1)
for i in range(M - 1):
    l, r = min(X[i], X[i + 1]), max(X[i], X[i + 1])
    d[1] += r - l
    d[l] += N - (r - l) - (r - l)
    d[r] += - N + (r - l) + (r - l)

ans = 100000000000
for i in range(1, N + 1):
    d[i] += d[i - 1]
    ans = min(ans, d[i])

print(ans)