[Python] 백준 2734: 드럼통 쌓기

🔗 문제 링크

2734번: 드럼통 쌓기

💊 문제 요약

드럼통을 눕혀서 직사각형 쓰레기통에 쌓으려고 한다. 테스트 케이스의 갯수 T가 주어지며, 각 케이스에서 초기에 놓으려는 드럼통의 갯수 N과 각 드럼통의 x 좌표 N개가 한 줄에 주어진다. 가장 아랫줄을 제외한 모든 줄은 바로 아랫줄의 드럼통 2개와 접하며, 바로 아래 줄보다 하나 적은 드럼통들이 있다. 가장 위에 쌓는 드럼통의 x와 y 좌표를 소수점 넷째자리까지 출력하라. 단, 드럼통 윗면의 반지름은 1이다.

🌿 풀이 설명

정답 코드

import sys
input=sys.stdin.readline

T=int(input().rstrip())
for _ in range(T):
    N, *drums=map(float, input().rstrip().split())
    N=int(N)
    drums_x=list(drums)
    init_drums=[]
    for i in range(N):
        init_drums.append((drums[i], 1))
    drums=[[] for _ in range(N)]
    drums[0]=sorted(init_drums)

    i=1
    for k in range(N-1, 0, -1):
        if i==1:
            for j in range(k):
                x1, y1=drums[i-1][j]
                x2, y2=drums[i-1][j+1]
                x=(x1+x2)/2
                y=y1+(4-((x2-x1)**2)*(1/4))**(1/2)
                drums[i].append((x, y))
        
        elif i>1:
            for j in range(k):
                x1, y1=drums[i-1][j]
                x2, y2=drums[i-1][j+1]
                ave_x, ave_y=(x1+x2)/2, (y1+y2)/2
                x3, y3=drums[i-2][j+1]

                dx, dy=ave_x-x3, ave_y-y3
                x=ave_x+dx
                y=ave_y+dy

                drums[i].append((x, y))
        i+=1
    print(f'{drums[N-1][0][0]:.4f} {drums[N-1][0][1]:.4f}')

드럼통 중심으로 그려지는 삼각형의 변 길이가 계산 가능하므로, 길이로 풀어보려 하였으나 관찰에 기반하여 우연히 발견한 각 드럼통 좌표의 관계성을 활용하여 문제를 해결하였다.

밀도있게 고민한 시간은 아니지만, 약 1시간 30분 정도 소요해서 푼 문제이다.

시도1: 드럼통 중심을 연결한 삼각형 변의 길이로 좌표를 정의

처음 한 것은, 위에 드럼통을 쌓았을 때 아래의 것이 굴러가서 위의 것이 떨어지는 경우가 있는지 확인하는 일이었다.

문제의 조건에서 드럼통의 간격은 2.0 이상, 3.4 이하로 주어져서 위의 드럼통이 떨어지지 않고 두 층 아래의 드럼통과도 접하지 않을 수 있어 보였는데, 실제로 그렇다는 것을 아래와 같이 검증할 수 있었다.

주어진 조건에서, 접한 드럼통의 중심을 이은 이등변 삼각형의 최소 높이는 1보다 크다.

 

첫 시도에서는 2층 드럼통의 좌표를 1층의 접한 드럼통들의 좌표로부터 구하고, 이를 일반화하여 문제를 해결하고자 하였다.

위 그림과 같이 드럼통의 중심을 이어 삼각형을 만들면 양변의 길이가 2인 이등변 삼각형이므로, 아래와 같이 dy를 구하여 2층 드럼통의 좌표를 구할 수 있다.

 

하지만, 이 방법은 2층 드럼통에서만 일반적으로 성립하고 3층 이상에서는 정답을 보증하지 못한다는 것을 예시 입출력 결과가 다른 것을 보고난 후 깨달았다.

아래에 접한 드럼통들의 높이가 다른 경우에는 삼각형의 높이가 y 좌표의 변화량으로 직결되지 않았던 것이다.

 

시도2: 드럼통 좌표의 대칭성 발견

이후에 아래의 접한 두 선을 연결한 직선의 수직선으로부터 좌표를 얻거나 삼각비를 활용해보려는 것과 같이 여러 시도를 하였으나, 방정식을 푸는 방법은 코드로 짜기에 무척 비효율적이라 느껴져서 계속해서 다른 방법을 모색했다.

영겁과 같은 시간이 흐르고... 그림을 가만히 보는데 규칙성이 보였다.

아래에 접한 두 드럼통과, 그 드럼통들에 동시에 접하는 드럼통이 좌표를 구하고자 하는 드럼통과 선대칭처럼 보였다.

'아 이거구나'하고 코드를 짜서 제출했는데, 정답이었다!

 

다시 문제를 살피는 지금, 이등변 삼각형을 넘어서 마름모를 발견하고 이를 통해 대칭성을 파악하는 것이 문제의 의도가 아니었을까하고 추측한다.

이 문제를 푼 것이 특별하게 느껴지는 이유는, 인터넷에도 따로 정답 코드나 설명이 없었던 문제였기 때문이다.
옛날이었다면 포기하였을 것 같은 문제라, 오늘따라 문제 해결한 것이 기분 좋다!