[Python] 백준 풀기 2477 - 참외밭

파이썬 백준 2477번

실버3

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

2477번: 참외밭

 

 

 

문제 보기

분류: 기하1, 수학, 구현, 기하학

 

 

 

문제 풀기

가장 긴 가로와 세로로 이루어진 직사각형 땅에서 참외밭만 해당하는 ㄱ형태의 땅만 선택하기 위해서는 필요 없는 부분을 제거해야 한다. 동서남북 방향으로 순차적으로 울타리를 제시해 주는데 이때 제외해야 하는 부분은 예제의 남3 동1 남3 동1과 같이 반복 형태를 띠게 된다. 제시된 입력의 순서에 따라 반복되는 위치가 달라지기 마련이기에 이것을 일치시켜주는 작업을 해줘야 제거해 줘야 하는 영역과 직사각형 전체의 영역을 찾는데 수월하다.

 

2차원 리스트의 형태로 입력받은 값은 반복 형태가 일어날 때까지 리스트 첫 번째 값을 마지막으로 넘겨주는 반복 작업을 수행해야 한다. 이 작업을 하는데 시간 복잡도에서 유리한 deque 를 불러와 사용하였다.

 

deque 안의 리스트가 ABABCD 형태로 위치될 때까지 while 을 실행시키고 ABAB 가 나타나면 while 을 종료한다.

    while True:
        if fence_ls[0][0] == fence_ls[2][0] and fence_ls[1][0] == fence_ls[3][0]:
            break
        pop_fence = fence_ls.popleft()
        fence_ls.append(pop_fence)

 

리스트의 방위가 ABABCD 형태로 정리되고 나면 두 번째(index 1) B 와 세 번째(index 2) C 에 해당하는 변의 곱은 제거 해 줘야 하는 넓이가 된다.

    removed_area = fence_ls[1][1] * fence_ls[2][1]

 

그리고, C 와 D 에 위치한 변은 전체 직사각형의 가로 세로의 길이가 되기에 둘의 곱으로 전체 넓이를 정할 수 있다.

    whole_area = fence_ls[4][1] * fence_ls[5][1]

 

이렇게 찾은 두 넓이의 차로 전체 참외의 개수를 return 해 줄 수 있다.

    return K * (whole_area - removed_area)    

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

from collections import deque

def fnNumberOfMelons(K, fence_ls):
    # 동서남북 index 가 ABABCD 형태로 반복 규칙이 일어날때까지 while 돌리기.
    while True:
        if fence_ls[0][0] == fence_ls[2][0] and fence_ls[1][0] == fence_ls[3][0]:
            break
        pop_fence = fence_ls.popleft()
        fence_ls.append(pop_fence)
        print(f'deque fence_ls: {fence_ls}')            # test print

    whole_area = fence_ls[4][1] * fence_ls[5][1]
    removed_area = fence_ls[1][1] * fence_ls[2][1]
    
    return K * (whole_area - removed_area)    
    

if __name__ == "__main__":
    fence_ls = deque()
    K = int(inputdata().strip())
    for _ in range(6):
        fence_ls.append(list(map(int, inputdata().split())))
    print(f'input fence_ls: {fence_ls}')        # test print

    result = fnNumberOfMelons(K, fence_ls)
    print(result)



# 7
# 1 60
# 3 20
# 1 100
# 4 50
# 2 160
# 3 30

# input fence_ls: deque([[1, 60], [3, 20], [1, 100], [4, 50], [2, 160], [3, 30]])
# deque fence_ls: deque([[3, 20], [1, 100], [4, 50], [2, 160], [3, 30], [1, 60]])
# deque fence_ls: deque([[1, 100], [4, 50], [2, 160], [3, 30], [1, 60], [3, 20]])
# deque fence_ls: deque([[4, 50], [2, 160], [3, 30], [1, 60], [3, 20], [1, 100]])
# deque fence_ls: deque([[2, 160], [3, 30], [1, 60], [3, 20], [1, 100], [4, 50]])
# deque fence_ls: deque([[3, 30], [1, 60], [3, 20], [1, 100], [4, 50], [2, 160]])

# 47600