[백준 2597번] : 줄자접기 파이썬 풀이

줄자접기

1 초

128 MB

1213

461

392

44.444%

문제

준성이는 1㎝ 간격으로 눈금이 매겨져 있는 줄자를 가지고 있다. 그 줄자에 있는 서로 다른 눈금 6개에 한 눈금에 하나씩 점이 찍혀 있는데, 빨간 점, 파란 점, 노란 점이 각각 두 개씩 있다.

준성이는 먼저 빨간 점이 만나도록 줄자를 접었다. 그런 후 두 파란 점이 만나도록 줄자를 접고, 또 다시 두 노란 점이 만나도록 줄자를 접었다. 줄자는 투명하여 접더라도 점들을 잘 볼 수 있다. 어떤 색깔의 두 점이 만나도록 줄자를 접었을 때, 그 다음에 접으려는 색깔의 두 점이 이미 만나고 있으면, 그 두 점에 대해서는 줄자를 접지 않는다.

예를 들어 길이 10㎝ 인 줄자에 아래 그림과 같이 2㎝ 와 7㎝ 위에에 두 빨간 점이 찍혀 있고, 5㎝ 와 4㎝위치에 파란 점이, 10㎝ 와 3㎝ 위치에 노란 점이 찍혀 있다고 하자. (그림에서 빨간 점은 별표로, 파란 점은 동그라미, 그리고 노란 점은 네모로 표시되어 있다.) 빨간 두 점이 만나도록 줄자를 접으면 줄자의 4.5㎝ 위치에서 접히고 4㎝ 와 5㎝ 눈금이 서로 만나게 된다. 그러면 줄자의 왼쪽 부분의 길이는 4.5㎝ 이고 오른쪽 부분의 길이는 5.5㎝가 되어, 접힌 줄자의 길이는 5.5㎝ 가 된다. 파란 두 점은 이미 만나므로 줄자를 접지 않고, 그런 다음 노란 두 점이 만나도록 접으면 줄자의 길이는 3.5㎝ 가 된다.

줄자의 길이와 각 색깔의 점들이 찍혀있는 위치가 주어질 때, 준성이가 빨간 색, 파란 색, 노란 색의 순서로 두 점이 만나도록 줄자를 접으면 줄자의 길이가 얼마가 되는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄자의 길이가 입력된다. 줄자의 길이는 10㎝ 이상, 1,000㎝ 이하이고 단위를 나타내는 ㎝은 입력되지 않는다. 둘째 줄에는 두 빨간 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 셋째 줄에는 두 파란 점의 위치가, 넷째 줄에는 두 노란 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 모든 점들의 위치는 서로 다르다.

출력

한 줄에 접은 후의 줄자의 길이를 소수점 이하 한자리까지 출력한다. 소수점 이하 한자리가 0 이면 0 도 출력한다.(예 4.0)

예제 입력 1 

10
2 7
5 4
10 3

예제 출력 1 

3.5

 

약간의 수학과 구현 알고리즘으로 해결할 수 있는 문제이다.

'접는다' 라는 개념이 낯설게 느껴져 다소 고민을 했었지만 차근차근 생각하면 된다.

 

먼저 접는 순서는 빨강 -> 파랑 -> 노랑의 순서를 가지며, 접은 후의 길이는 접힌 부분과 접히지 않는 부분의 길이 중 더 긴 길이를 채택한다.

 

예를 들어 문제와 같이 4.5를 기준으로 접을때 아래와 같은 모양이 될 것이다.

 

위는 기존의 위치이고, 아래는 접힌 부분을 표시한 것이다. 4.5~10까지의 길이가 더 길기 때문에 전체 종이의 길이는 10-4.5가 된다.

 

그럼 이제 점들의 좌표를 어떻게 변경할까의 문제이다.

 

문제의 예시를 기준으로 빨간점 (2,7)이 접혔을때의 중간지점(접히는 지점)을 알기 위해 두 수의 평균을 구한다.

=> (2 + 7 )/ 2 = 4.5

 

4.5라는 좌표를 기준으로 두 점을 접게되므로, 다른점들도 새로운 좌표로 이동하게 되는데 여기서 당연하게도 접히는 지점보다 오른쪽에 있는 수들은 움직이지 않고 위치가 고정될 것이다. 위 예시에서 파란점5, 빨간점7, 노란점10이 이에 해당한다.(4.5<5, 7, 10)

 

새로운 좌표는 대칭 이동이므로, 기준점(위 예시에서는 빨간색 점)들의 합에 맞춰 대칭이동을 수행하면 된다.

따라서 파란점 4는 9(2+7) - 4 한 값인 5로 이동하게 될 것이며, 노란점 3은 9 - 3 = 6이므로 좌표 6으로 이동하게 된다.

 

위 알고리즘을 적용한 다른 예시는 아래와 같다. 편의상 빨,파,노는 r,b,y로 적었다.

0 1 2 3 4 5 6 7 8 9 10
    b b   y y r r 

# r 접기
7+8 = 15, 중간점 7.5, 전체 길이 (10-7.5 = 2.5) < (7.5-0 = 7.5) => 7.5
7.5 8 9 10 11 12 13 14 15
    r y  y     b  b

# b 접기
12 + 13 = 25, 중간점 12.5, 전체 길이 (15-12.5 = 2.5) < (12.5-7.5 = 5) => 5
12.5 13 14 15 16 17 17.5
b           y  y

# y 접기
15 + 16 = 31, 중간점 15.5, 전체길이 (17.5-15.5=2) < (15.5-12.5=3) => 3

 

이 알고리즘을 코드로 옮기면 아래와 같다. 편의를 위해 반복문을 사용하여 중복을 최소화하였다.

 

start = 0 # 시작 좌표는 0
end = int(input()) # 끝 점의 좌표
length = end-start+1
colors = [list(map(int,input().split())) for _ in range(3)]
for i,color in enumerate(colors):
    # 만약 두 점의 좌표가 같다면 해당 색상에 대해서는 이동하지 않는다.
    if color[0] == color[1]:
        continue
    # 중간점 구하기
    color_sum = sum(color)
    mid = round(color_sum/2,1) # 소수점 첫째자리까지
    # 전체 길이 구하기
    length = max((end-mid),(mid-start))
    # 새로운 시작점, 끝점 구하기
    start = mid
    end = start + length
    # 좌표 이동
    # 현재 움직인 좌표 이후의 색에 대해서만
    for j in range(i,len(colors)):
        for k in range(2):
            if colors[j][k] < mid: # 중간점보다 왼쪽에 있는 경우에만 새로운 좌표로 움직인다.
                colors[j][k] = color_sum - colors[j][k]
print(length)

 

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

2784번: 가로 세로 퍼즐