[ICPC 본선 대비 뇌셋] Day 14

백준 20077번 Wiring www.acmicpc.net/problem/20077

20077번: Wiring

IOI기출은 처음 풀어보는듯..? 문제가 되게 좋았다. 물론 코딩은 안했다.ㅋㅋ 생각도 나름 오랫동안 한거같다. 섭테를 보고 힌트를 좀 얻은것 같기도 하다.

 

[관찰 1] 그림과 같이 최적의 상황에서 파랑과 빨강은 연속한 블록에서만 이어져야 한다.

관찰 1의 그림

[관찰 2] 그림과 같이 두 그룹간의 간선이 겹치면 안된다.

관찰 2의 그림

따라서 최적의 경우는 다음과 같이 노란색 그룹 안에서만 연결이 일어나야한다.

관찰 3의 그림

그리고 각 그룹에서 노드 사이의 거리는 최소 그림 위에 적혀있는 숫자만큼 사용되고, 이것을 만족하는 실례는 아래의 그림 아래의 연결과 같다.

그룹 내에서의 최소길이 연결

이제 DP를 돌아주면 된다. i번째 위치까지 사용했을 때 사용된 길이의 최솟값을 A[i]라고 하자. A[N]이 우리가 구하고자하는 답이다.

j를 i가 있는 블록의 왼쪽 블록이라고 하자.

인덱스를 신경써서 작성하지는 않았다. 그냥 이런 느낌으로 코딩하면 된다는 뜻.

$BR[j] = \sum{ dist[k]*(k-j) }$, k : j의 오른쪽에 있는 같은 블록의 노드

$BL[j] = \sum{ dist[k]*(j-k) }$, k : j의 왼쪽에 있는 같은 블록의 노드

는 쉽게 구할 수 있다.

다음 두가지 값을 저장해주면서 DP를 돌면 된다.

C[j] = A[j] + BR[j]

j블록과 i블록이 연결되는 지점의 길이를 w, 그 지점의 인덱스를 k라고 하자.

D[j] = A[j] + BR[j] + w*(k-j)

이때, $A[i] = min(min(C[j]+BL[i]+w*(i-k) : k-j < i-k), min(D[j]+BL[i] : k-j >= i-k))$

각 min는 잘 저장해놓을 수 있다. 따라서 선형시간 안에 가능.

 

문제를 풀면서 내가 너무 그리디에 집착하는 느낌을 받았다. 이걸 고치면 좀 더 빠르게 생각할 수 있을 것 같다.

 

[수정] 블록이 하나의 노드로 이루어져 있으면, 그 노드는 양 옆의 블록과 연결할 수 있다. 따라서 이 경우를 예외처리해줘야한다.

+ 다른 풀이를 봤는데 느낌이 좀 다르고 더 간결하다. 이 풀이는 검증이 필요할듯 하다.