[백준] 마라톤 1

쏠로몬·2021년 10월 17일
0

접근 방법 : 브루트 포스

처음에 deepcopy를 써서 전체에서 하나 씩 삭제한 뒤, 합을 구하려 했는데 실패했다.

전체 합에서 체크 포인트 하나 빼기 위한 최대 포인트 계산 값을 확인
뺄 체크 포인트 기준은 제일 큰 게 빠졌을 때 최소가 되니 최대값을 구해준다.

# -*- coding: utf-8 -*-
import sys

N = int(sys.stdin.readline().strip())
check_list = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
check_dist = 0
total_sum = 0

for i in range(N - 1):
    total_sum += abs(check_list[i][0] - check_list[i + 1][0]) + abs(check_list[i][1] - check_list[i + 1][1])

for i in range(1, N - 1):
    left_dist = abs(check_list[i - 1][0] - check_list[i][0]) + abs(check_list[i - 1][1] - check_list[i][1])
    right_dist = abs(check_list[i + 1][0] - check_list[i][0]) + abs(check_list[i + 1][1] - check_list[i][1])
    skip_dist = abs(check_list[i + 1][0] - check_list[i - 1][0]) + abs(check_list[i + 1][1] - check_list[i - 1][1])
    sub_dist = left_dist + right_dist - skip_dist
    check_dist = max(check_dist, sub_dist)

print(total_sum - check_dist)
profile
이사가요~ 티스토리 블로그 입니다. https://help-solomon.tistory.com/

0개의 댓글