2564

날짜 : 2023. 02. 15

사용 언어 : python

 

문제

 

 

코드

import sys

w, h = map(int, sys.stdin.readline().split())  # 가로, 세로
s = int(sys.stdin.readline()) # 상점 개수
store = list() # 펼쳤을 때의 위치(동근 포함)


# 펼쳤을 경우 북(1)->동(4)->남(2)->서(3)
def cal(p, d):
    if p == 1: # 북
        return d
    elif p == 4: # 동
        return w + d
    elif p == 2: # 남
        return w + h + w - d # 거리를 빼거나 더하는 경우 주의
    elif p == 3: # 서
        return w + h + w + h - d


# 각 거리 계산(동근 포함)
for _ in range(s+1):
    pos, dist = map(int, sys.stdin.readline().split()) # 방향, 위치
    store.append(cal(pos, dist))
#print(store)

cur = store.pop() # 동근
total = 2 * (w + h) # 전체 변의 길이의 합
res = 0

for i in range(s):
    cal_dist = abs(cur - store[i]) # 이동거리 계산
    #print(cal_dist, total - cal_dist)
    res += min(cal_dist, total - cal_dist) # 역방향으로 이동했을 때의 거리 계산
    
print(res)

 

 

풀이

- 직사각형의 좌상단 꼭지점을 기준으로 오른쪽으로 쭉 펼쳤을 때를 구현한 후 절대거리를 구현한다.

- 절대거리 구현 시 각 방향과 거리를 고려하여 분기하여 구한다.

- 그 다음 동근이의 위치를 추출한 후 각 지점마다의 거리의 최솟값을 구하여 누적합을 구한다.

 

 

알게된 점

- 문제를 잘못봐도 완전히 잘못봤다.

- 동근이 위치 ~ 각 지점마다의 거리의 누적합인데 각 지점을 탐색하는 경로의 최솟값을 구하는 것으로 문제를 이해했다.

- 문제를 제대로 이해하고 접근하니까 오히려 곧바로 풀려서 상당히 자괴감이.... 든다. (1시간 넘게 고민했는데...)

 

 

참고 사이트

- https://sjy1218vv.tistory.com/201

[알고리즘]BOJ_2564_경비원(파이썬)