[Python][백준] 10655. 마라톤 1/ 구현, 브루트포스 (S3)

링크🔗

https://www.acmicpc.net/problem/10655

---

🗒️파이썬 코드 풀이

N = int(input())

x_lst = []
y_lst = []

for _ in range(N):
    x,y = map(int,input().split())
    x_lst.append(x)
    y_lst.append(y)

sum = 0 
for i in range(0,len(x_lst)-1):
    sum = sum + abs(x_lst[i]-x_lst[i+1]) + abs(y_lst[i]-y_lst[i+1])

mn = 1e100
for i in range(1,len(x_lst)-1):
    prev_mid = abs(x_lst[i-1] - x_lst[i]) + abs(y_lst[i-1] - y_lst[i])
    mid_end = abs(x_lst[i] - x_lst[i+1]) + abs(y_lst[i] - y_lst[i+1])
    prev_end = abs(x_lst[i-1] - x_lst[i+1]) + abs(y_lst[i-1] - y_lst[i+1])

    fix_value = -(prev_mid + mid_end) + prev_end    
    mn = min(mn, sum-fix_value)

print(mn)

 

1. 입력으로 받은 값들을 x,y로 나누어 x_lst, y_lst에 담아준다.

 

2. 모든 좌표들의 거리들을 구하고 더해준다. 

ex)
1) (0,0) (8,3) 거리
2) (8,3) (11,-1) 거리
3) (11,-1) (10,0) 거리

 

3. 아주 넉넉게 초기 최소값은 선언한다.  (초반에 바로 갱신 가능하도록)

(최소값을 10만으로 했다가, 초기값 갱신이 안되서 정답처리가 안됐다.)

 

4. 첫번째와 마지막 체크포인트를 제외한 만큼의 반복문을 돌리고,

중간의 특정 체크포인트를 한개 빼준다.  

ex) (0,0) (8,3) / (8,3) (11,-1) 에서 (8,3) 체크포인트를 제거하는 경우 :

모든 체크포인트 합 - (0,0)(8,3)거리 - (8,3)(11,-1)거리 + (0,0)(11,-1)거리
결국에는 - ((0,0)(8,3)거리+(8,3)(11,-1)거리) + (0,0)(11,-1)거리의 최대값을 구하면 된다.

 

✏️ 실패한 내 코드 풀이

from itertools import combinations

N = int(input())

x_lst = []
y_lst = []

for _ in range(N):
    x,y = map(int,input().split())
    x_lst.append(x)
    y_lst.append(y)

x_remove_lst = list(combinations(x_lst[1:N-1],N-3))
y_remove_lst = list(combinations(y_lst[1:N-1],N-3))
mn = 10000000

for i in range(len(x_remove_lst)):
    X = [0] + list(x_remove_lst[i]) + [x_lst[N-1]]
    Y = [0] + list(y_remove_lst[i]) + [y_lst[N-1]]
    print(X,Y)
    sum_X,sum_Y = 0,0
    for k in range(len(X)-1):
        sum_X += abs(X[k] - X[k+1])
        sum_Y += abs(Y[k] - Y[k+1])

    mn = min(mn,sum_X+sum_Y)  
    
print(mn)

 

1. 조합을 이용해서 1개의 체크포인트를 뺀 경우의 리스트를 모두 저장하고,

그 리스트들의 합을 구하여 가장 최소값을 찾는 방법으로 했다. 

 

2. 당연히 시간 초과가 발생했다 ...

(N<= 100000의 범위여서 안된다 ㅠㅠ)

 

📌  문제 코멘트

 

문제를 처음 읽었을때 체크포인트를 한개씩 여러번 뛰어도 되는줄 알고,

구현에 멘붕이 왔었다...

 

다행이 1개의 체크포인트만 생략하는 문제였는데, 

그래도 구현이 좀 어려웠다. 

 

최대한 시간 복잡도를 고려해서 잘 풀어보자 !! 

---

📚문제

농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.

마라톤 코스는 N (3 ≤ N ≤ 100000) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한개를 몰래 건너뛰려 한다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.

젖소 박승원이 체크포인트 한개를 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?

참고로, 젖소 마라톤 대회는 서울시내 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다. 즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)

입력

첫 번째 줄에 체크포인트의 수 N이 주어진다.

이후 N개의 줄에 정수가 두개씩 주어진다. i번째 줄의 첫 번째 정수는 체크포인트 i의 x좌표, 두 번째 정수는 y좌표이다. (-1000 ≤ x, y ≤ 1000)

체크 포인트의 좌표는 겹칠 수도 있다 - 젖소 박승원은 체크포인트를 건너뛸 때 그 번호의 체크포인트만 건너뛰며, 그 점에 있는 모든 체크포인트를 건너뛰지 않는다.

출력

젖소 박승원이 체크포인트 1개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.

예제 입력 1 복사

4
0 0
8 3
11 -1
10 0

예제 출력 1 복사

14