[백준][파이썬] 2477 참외밭

1.문제 분석

• 도형의 넓이를 구하는 문제
• 넓이를 분리하는 문제

---

2. 기본 아이디어

1. 큰 직사각형의 넓이에서 작은 직사각형의 넓이를 뺀다.
2. 작은 직사각형의 크기를 구하는 방식을 찾아낸다.

---

3.문제 풀이

이 문제의 경우, 큰 넓이에서 작은 넓이를 빼는 아이디어는 발견했지만

작은 직사각형의 넓이를 구하는 데에 고민이 많았던 문제다.

 

첫번째 풀이( 틀림 )

 

n = int(input())
hz_max, hz_min, vt_max, vt_min = 0, 500, 0, 500  # 가로 세로의 가장 긴, 짧은 길이

for i in range(6):
    lst = list(map(int, input().split()))

    if(lst[0] == 1 or lst[0] == 2):   # 가로 길이라면
        hz_max = max(lst[1], hz_max)  # 가로 최대 길이
        hz_min = min(lst[1], hz_min)  # 가로 최소 길이

    elif (lst[0] == 3 or lst[0] == 4): # 세로 길이라면
        vt_max = max(lst[1], vt_max)   # 세로 최대 길이
        vt_min = min(lst[1], vt_min)   # 세로 최소 길이

print((hz_max*vt_max - hz_min*vt_min) * n)

 

이 방식이 틀린 이유는

 

 

이러한 형태의 넓이를 구할 수 없기 때문이다.

큰 직사각형의 넓이는 손쉽게 구할 수 있지만, 세로의 최소 길이는 b가 아닌 a가 되므로

작은 직사각형을 구하는 과정에서 논리적인 오류가 발생한다.

따라서 다른 방식을 통해 이 문제를 풀어야 할 것이다.

---

두번째 풀이

아무리 고민해도 어려웠다.

구글링을 통해 힌트를 살짝 봤다.

그 아이디어를 토대로 구현한게 아래의 코드다.

 

n = int(input())
hz_max, hz_max_idx, vt_max, vt_max_idx = 0, 0, 0, 0 # 최대 가로 세로와 그 인덱스를 저장
lines = []    

for i in range(6):  # 육각형이므로 6번 선을 그을 수 있다.
    lst = list(map(int, input().split()))
    lines.append(lst)    # 선분의 방향과 길이를 저장해둔다.

    if(lst[0] == 1 or lst[0] == 2):  # 가로 방향일 경우
        if(lst[1] > hz_max):
            hz_max = lst[1]      
            hz_max_idx = i    # 최대 길이의 인덱스를 저장해둔다.

    else:
        if (lst[1] > vt_max):  # 세로 방향일 경우
            vt_max = lst[1]
            vt_max_idx = i     # 최대 길이의 인덱스를 저장해둔다.

# 최대 가로 세로의 양 옆 변들을 저장해둔다.
lines_list = [lines[hz_max_idx - 1], lines[(hz_max_idx + 1) % 6], lines[vt_max_idx - 1], lines[(vt_max_idx + 1) % 6]]

small_square = 1
for line in lines:
    if line not in lines_list:     # 최대 가로 세로의 양 옆이 아닌 변이라면
        small_square *= line[1]    # 작은 직사각형의 가로 세로일 것이다.

ans = (hz_max * vt_max - small_square) * n
print(ans)

 

왜 문제를 이렇게 풀 수 있었을까?

우선 최대 가로 세로의 인덱스를 저장했다.

문제의 입력은 반시계 방향으로 도형을 그리는 것과 같다.

 

 

받은 입력들을 리스트에 순서대로 넣는다면, 최대 가로 ( C ) 의 양 옆에는 a와 D가 있을 것이다.

또한 최대 세로 D의 양 옆에는 C와 e가 있을 것이므로, 결국 남는 것은 f와 b

 

(** 위 두 문장을 보면 잘 알겠지만, lines_list에 최대 길이의 변도 같이 넣지 않는 이유는

      최대 가로, 세로의 양 옆 변에는 무조건 또다른 최대 길이의 세로, 가로가 인접해 있기 때문이다.)

 

즉, 작은 직사각형의 가로, 세로만 남는다.

따라서, 위 코드의 small_square을 구하는 과정이 바로 f와 b를 구하는 과정인 것이다.