[백준] 2477 - 참외밭

728x90

문제 링크

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

문제 요약

태양이는 참외밭에서 자라는 총 참외의 개수를 알고 싶어합니다. 이를 위해 1m²당 자라는 참외의 개수 K와 참외밭의 넓이를 구해야 합니다.

참외밭은 특정한 형태의 육각형이며, 각 변은 동서남북 방향 중 하나를 가지며 길이가 주어집니다. 이때, 참외밭의 넓이를 구한 후 K를 곱하여 전체 참외의 수를 계산해야 합니다.

푼 방법

• 참외밭의 넓이 계산:
  • 참외밭은 특정한 형태의 육각형이지만, 실질적으로는 큰 사각형에서 작은 사각형을 뺀 형태입니다.
  • 큰 사각형은 가장 긴 가로 변과 가장 긴 세로 변의 곱으로 구할 수 있습니다.
  • 작은 사각형은 중간에 있는 비어있는 부분으로, 연속된 변의 방향 패턴을 찾아 그 넓이를 계산합니다.
• 작은 사각형 찾는 방법:
  • 변의 방향이 연속적으로 두 번씩 반복되는 지점을 찾아냅니다.
  • 이 지점이 작은 사각형의 시작점이 됩니다.
  • 예를 들어, 변의 방향이 [4, 2, 3, 1, 3, 1]로 주어졌을 때, [4, 2]와 [3, 1]이 반복됩니다.
  • 이때 lines[1]과 lines[2]가 작은 사각형의 변의 길이가 됩니다.
• 최종 계산:
  • 전체 넓이 = 큰 사각형 넓이 - 작은 사각형 넓이
  • 전체 참외의 수 = 전체 넓이 * 1m²당 참외의 수 K

정답 코드

from collections import deque
k = int(input())
hori = []
vert = []
seq=deque()
lines=deque()
for i in range(6):
    index, outline = map(int, input().split())
    seq.append(index)
    lines.append(outline)
    if index == 1  or index == 2:
        hori.append(outline)
    else:
        vert.append(outline)
while True:
    if seq[0] == seq[2] and seq[1]==seq[3]:
        small=lines[1]*lines[2]
        break
    seq.append(seq.popleft())
    lines.append(lines.popleft())
print((max(hori) * max(vert) - small) * k)

배웠던 부분

• 여기에 배운 내용을 나열하세요.
• 예: 새로운 알고리즘 패턴, 최적화 방법