백준 [10986] 참외밭(Python3)

문제 링크 : https://www.acmicpc.net/problem/2477

2477번: 참외밭

 

완전 탐색 선에서 해결할 수 있는 문제. 처음엔 ㄱ 형태를 통해 만들어진 온갖 형태를 고려해야 하나 걱정했는데 지문에서 6각형이고, 이동한 순서대로 입력이 들어온다고 써져있어 쉽게 풀 수 있었다.

 

파이썬이 인덱스 처리에 관대하기 때문에 파이썬을 쓴다면 생각보다 쉽게 풀 수 있다.

먼저 큰 직사각형의 넓이를 구한 뒤, 공백이 생기는 작은 사각형의 넓이를 구해 빼는 식으로 문제를 해결했다.

 

하지만, 이 작은 사각형이 어떤 길이로 구성되는지에 대한 기준을 세워야 한다.
예시에선 x,y 에서 각각 제일 작은 값 2개 골라서 빼면 답이 나오는 거 같지만 일부 케이스에선 그렇지 않다.

반례

7
4 50
2 160
3 20
1 60
3 30
1 100
wrong : 47600
answer : 43400

 

도형을 계속 관찰하다 보면 다음과 같은 사실을 알 수 있다.
공백이 생기는 작은 사각형의 변과 연결되는 변들은 x나 y의 최대 값 중 하나가 아니다.
이를 이용해 완전탐색 풀이를 세우면 다음과 같다.

 

완전 탐색

6개의 변의 정보를 받을 때, x와 y축의 최대값을 구하면서 리스트에 저장한다.

그 후, 리스트를 순회하면서 지나온 길이가 x축이나 y축의 최대값이 아닐 때,
이를 이용해 앞뒤 인덱스에서 x축이나 y축의 최대값을 지나간 적이 있는지 확인한다.
하나라도 그런 적이 있다면 넘어가고 양쪽 다 최대값이 아니라면 해당 수 끼리 곱한다. 이렇게 곱해진 수를 t라 하자.

그 후, x, y의 최대값의 곱과 t를 뺀 뒤, K를 곱하면 답이 나온다.

 

코드

K = int(input())
maxX, maxY = 0, 0
nums = []
for _ in range(6):
    d, l = map(int, input().split())
    if d == 1 or d == 2:
        maxX = max(maxX, l)
    else:
        maxY = max(maxY, l)
    nums.append([d, l])
ans = 1
for i in range(len(nums)):
    if nums[i][1] == maxX or nums[i][1] == maxY:
        continue
    else:
        if not (nums[(i - 1) % 6][1] == maxX or nums[(i - 1) % 6][1] == maxY or nums[(i + 1) % 6][1] == maxX or nums[(i + 1) % 6][1] == maxY):
            ans *= nums[i][1]
print(((maxX * maxY) - ans) * K)