[백준/Python] 1184 귀농

📌문제 탐색하기

• 크기가 NxN인 정사각형의 땅이 있고, 땅은 단위 정사각형 1x1로 나누어져 있음
  • 각 단위 정사각형(i,j)의 수익은 A(i,j) (음수가 될 수도 있음)
• 땅의 일부를 두 사람에게 나눠주고자 함
  • 두 사람이 받게되는 땅은 항상 직사각형 모양이고, 변은 축에 평행
• 두 사람이 농사지을 땅의 수익의 합이 같게 되도록 하며, 두 땅이 꼭짓점 하나에서만 만나도록 하는 방법의 수 구하기
  • 두 땅이 변을 공유할 수는 없음

입력

• 땅의 크기 N (1 ≤ N ≤ 50)
• N개의 줄에 걸쳐 N개의 숫자가 주어지며, A(i,j)는 부분 정사각형 (i,j)의 수익 (-1000 < A(i,j) < 1000)

출력

• 조건을 만족하면서 땅을 빌려주는 방법의 수 출력

풀이 방법 생각해보기

첫번째 사람이 받을 수 있는 땅을 먼저 브루트포스 탐색하고, 각 선택된 땅에 대해 오른쪽 위 꼭짓점 또는 오른쪽 아래 꼭짓점 하나만 공유하되, 첫번째 사람이 받은 땅의 수익과 두번째 사람이 받은 수익이 같도록 땅을 선택하는 가짓수를 구하면 된다. (모든 꼭짓점에 대해 경우의 수를 구해버리면 중복이 발생하므로 오른쪽 위, 오른쪽 아래 2개만 확인)

 

이때, (0, 0)부터 (i,j)까지의 땅을 선택했을 때의 누적합을 구해 선택된 땅의 수익을 구하기 용이하게 한다.

 

 📌코드 설계하기

1. 땅의 크기 N을 입력받는다.
2. 각 단위 정사각형 땅의 수익을 저장할 이차원 리스트 profit을 생성하고, 값을 입력받는다.
3. 방법의 수를 저장할 변수 count를 생성하고 0으로 초기화한다.
4. (0,0)을 왼쪽 위 꼭짓점으로 하고 (i,j)을 오른쪽 아래 꼭짓점으로 하는 직사각형으로 땅을 선택했을 때, 모든 땅의 수익을 저장할 (N+1)x(N+1) 이차원 리스트 prefix_profit을 생성한다.
5. prefix_profit을 순회하면서, prefix_profit(i,j)에 대해 prefix_profix(i-1, j) + prefix_profit(i, j-1) - prefix_profit(i-1,j-1) + profit(i-1, j-1)를 저장한다.
6. (i,j)를 왼쪽 아래 꼭짓점으로 가지는 직사각형의 수익에 대해 가짓수를 저장할 (N+1)x(N+1) 이차원 리스트 left_bottom_rectangle과 마찬가지로 (i,j)를 왼쪽 위 꼭짓점으로 가지는 직사각형의 수익에 대해 가짓수를 저장할 이차원 리스트 left_top_rectangle을 생성하고, 모든 요소를 defaultdict(int)로 초기화한다.
   • 예를 들어, left_bottom_rectangle[x][y][n]은 (x,y)를 왼쪽 아래 꼭짓점으로 갖는 직사각형 영역 중 수익이 n인 영역의 가짓수를 저장함 
7. (1 ≤ x1 < N, 1 ≤ y1 < N), (x1 < x2 < N+1, y1 < y2 < N+1)의 범위로 4중 for문 탐색하면서 나올 수 있는 모든 직사각형 영역의 경우를 구한다. 이후, 해당 직사각형 영역의 수익을 구하고, left_bottom_rectangle[x2][y1][수익]과 left_top_rectangle[x1][y1][수익] 각각에 1을 더한다.
8. 4중 for문을 통해 첫번째 사람이 가져갈 땅의 왼쪽 위 꼭짓점 (x1,y1), 오른쪽 아래 꼭짓점 (x2,y2)의 경우의 수를 모두 구하고, 각 경우에 대해 수익을 구해서 left_bottom_rectangle[x1][y2][수익]과 left_top_rectangle[x2][y2]를 count에 더한다.
9. count를 출력한다.

 

📌시도 회차 수정사항

• 1회차 (시간초과)

import sys
input = sys.stdin.readline

N = int(input())
profit = [list(map(int, input().split())) for _ in range(N)]
count = 0

prefix_sum_profit = [[0]*(N+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, N+1):
        prefix_sum_profit[i][j] = prefix_sum_profit[i][j-1] + prefix_sum_profit[i-1][j] - prefix_sum_profit[i-1][j-1] + profit[i-1][j-1]


def get_total_profit(x1, y1, x2, y2):
    return prefix_sum_profit[x2][y2] - prefix_sum_profit[x1][y2] - prefix_sum_profit[x2][y1] + prefix_sum_profit[x1][y1]

def find_valiable_cases(x1, y1, x2, y2):
    global count
    current_total_profit = get_total_profit(x1, y1, x2, y2)
    
    for a in range(x1):
        for b in range(y2, N+1):
            if get_total_profit(a, y2, x1, b) == current_total_profit:
                count += 1
    
    for a in range(x2+1, N+1):
        for b in range(y2+1, N+1):
            if get_total_profit(x2, y2, a, b) == current_total_profit:
                count += 1


for x1 in range(N):
    for y1 in range(N):
        for x2 in range(x1+1, N+1):
            for y2 in range(y1+1, N+1):
                find_valiable_cases(x1, y1, x2, y2)
            
    
print(count)

 

위와 같이 O(N⁶)의 시간복잡도를 갖는 코드를 제출했다. 결과는 역시 시간초과.

 

위 코드를 "첫번째 영역의 좌표를 구하고, 오른쪽 위 꼭짓점을 공유하거나 오른쪽 아래 꼭짓점을 공유하는 영역 중 첫번째 영역 수익이랑 같은 것 개수 구하기"라는 기본 로직은 똑같이 가져간 채로 수정했다.

첫번째 영역이 결정되면 두번째 영역을 완전탐색(O(N²))하는 것이 아니라, 미리 해시맵을 통해 오른쪽 위 꼭짓점을 가지는 영역에서 나올 수 있는 수익의 가짓수, 오른쪽 아래 꼭짓점을 가지는 영역에서 나올 수 있는 수익의 가짓수를 구해두고 이를 활용(O(1))하도록 수정했다. 

 

 

📌 정답 코드

from collections import defaultdict

import sys
input = sys.stdin.readline

N = int(input())
profit = [list(map(int, input().split())) for _ in range(N)]

prefix_profit = [[0]*(N+1) for _ in range(N+1)]

for i in range(1, N+1):
  for j in range(1, N+1):
    prefix_profit[i][j] = prefix_profit[i-1][j] + prefix_profit[i][j-1] - prefix_profit[i-1][j-1] + profit[i-1][j-1]

left_bottom_rectangle = [[defaultdict(int) for _ in range(N+1)] for _ in range(N+1)]
left_top_rectangle = [[defaultdict(int) for _ in range(N+1)] for _ in range(N+1)]

for x1 in range(N):
  for y1 in range(N):
    for x2 in range(x1+1, N+1):
      for y2 in range(y1+1, N+1):
        current_rectangle = prefix_profit[x2][y2] - prefix_profit[x1][y2] - prefix_profit[x2][y1] + prefix_profit[x1][y1]
        left_bottom_rectangle[x2][y1][current_rectangle] += 1
        left_top_rectangle[x1][y1][current_rectangle] += 1

count = 0

for x1 in range(N):
  for y1 in range(N):
    for x2 in range(x1+1, N+1):
      for y2 in range(y1+1, N+1):
        current_rectangle = prefix_profit[x2][y2] - prefix_profit[x1][y2] - prefix_profit[x2][y1] + prefix_profit[x1][y1]
        count += left_bottom_rectangle[x1][y2][current_rectangle]
        count += left_top_rectangle[x2][y2][current_rectangle]

print(count)