[파이썬/python] 백준 - 2597 줄자접기

문제

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

---

문제 설명

1.   서로 다른 눈금 6개(빨간 점, 파란 점, 노란 점)가 있는 1cm 간격의 줄자가 존재한다.
2. 빨간 점, 파란 점, 노란 점 순서로 두 점이 겹치게 줄자를 접는다.
   1. 이 때 이미 두 점이 접혀있으면, 다음 점으로 넘어간다.
3. 모든 점을 겹치게 접었을때 줄자의 길이를 구한다.   

 

---

풀이

두 점이 접힐 때 상황을 보자.

 

길이가 10인 줄자가 존재한다.

빨간 점 : 2,7

노란 점 : 3, 10

파란 점 : 4, 5

 

빨간 점을 겹치도록 접으면 (2 + 7) // 2 = 4.5 위치에서 접힌다.

줄자는 4.5, 전체 - 4.5의 길이로 분리가 되고 접혔을 때 전체 길이는 두 길이 중 큰 길이가 될 것이다.

 

위 과정을 3번 반복하게 되면 최종 줄자의 길이가 나오게 된다.  

1. 세 점을 순서대로 탐색한다.
   1. 이미 두 점이 겹쳐있다면 다음 점으로 넘어간다.
   2. 중앙을 찾고 접혔을 때의 위치를 갱신한다.
   3. 접힌 후 점들의 위치를 갱신한다.
2. 줄자의 최종 길이를 출력한다.

---

코드

import sys
input = sys.stdin.readline
length = int(input())
dot = [list(map(int,input().split())) for _ in range(3)]

for i in range(3):
    if dot[i][0] == dot[i][1]:
        continue
    
    mid = sum(dot[i]) / 2
    length = max(length-mid, mid)
    
    for j in range(i+1,3):
        for k in range(2):
            dot[j][k] = abs(dot[j][k]-mid)

print(f'{length:.01f}')

---

시간복잡도

• 단순 3번만 반복하기 때문에 약 O(1) (상수) 정도의 시간복잡도가 소요된다.