[백준/1460] 진욱이의 농장 (Python3)

Problem :https://www.acmicpc.net/problem/1460

1460번: 진욱이의 농장

 

Difficulty : Gold 3

 

Status : Solved (pypy3)

 

Time : 00:29:57

 

---

 

문제 설명

 

진욱이는 N×N 크기의 정사각형 농장을 가지고 있다. 농장은 1*1크기의 칸으로 나누어져 있고, 각 칸은 한 종류의 과일이 심어져 있다. 가장 처음에 농장에는 모두 0번 과일만 심어져 있다. 

진욱이는 총 씨앗을 M번 뿌리려고 한다. 이때, 씨앗을 뿌리는 방벙은 네 정수 X, Y, L, F로 나타낼 수 있다. 여기서 (X, Y)는 정사각형의 왼쪽 위 모서리 좌표이고, L은 정사각형 변의 길이, F는 씨앗의 종류이다. 만약, 씨를 이미 뿌린 곳에 또 뿌리는 경우에는, 원래 심어져있던 씨가 없어지고, 새로운 씨가 심어지게 된다. 가장 왼쪽 위 모서리의 좌표는 (0, 0)이다.

진욱이는 군대에 입대하기 전에 준규에게 농장의 일부를 주고 가려고 한다. 준규가 정사각형 모양으로 농장을 가져갈 수 있다. 이때, 정사각형에 포함된 과일의 종류는 최대 두 종류이어야 하고, 0번 과일은 가져갈 수 없다.

준규가 가져갈 수 있는 가장 넓은 농장의 넓이를 구하는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

첫째 줄에 두 정수 농장의 크기 N과 씨앗을 뿌린 횟수 M이 주어진다.

둘째 줄부터 M개의 줄에는 씨를 뿌린 방법이 주어진다. 각각의 줄은 네 정수 X, Y, L, F로 이루어져 있다.

 

출력

준규가 가져갈 수 있는 가장 넓은 정사각형의 넓이를 출력한다.

 

제한

• 1 ≤ N ≤ 1,000
• 1 ≤ M ≤ 50
• 0 ≤ X, Y ≤ N-1
• 1 ≤ L ≤ N
• 1 ≤ X+L, Y+L ≤ N
• 0 ≤ F ≤ 7

 

입력 예시

7 3
0 0 7 7
2 2 4 1
3 5 1 5

 

 

출력 예시

25

 

 

---

 

풀이

 

최대 2개의 과일 종류를 포함하는 (0은 제외) 가장 큰 정사각형을 찾아야 한다. 여기서 딱 DP를 떠올렸다.

 

과일 종류는 많아봐야 7가지이므로, 과일 2개를 뽑는 O(F^2)의 시간복잡도 내에 DP를 사용하면 총 시간복잡도는 O(F^2 * N^2)을 만족한다. (하지만 이조차도 그냥 Python3에서는 느리다)

 

DP 자체는 최대 정사각형 면적을 구하는 케이스이므로, 그렇게 어렵진 않으나 개념 정리 겸 짚고 넘어가고자 한다. 여기서 dp[i][j]는 (i, j)를 오른쪽 아래 꼭지점으로 가지는 정사각형 중 조건을 만족하는 최대 정사각형 넓이를 의미한다. 다음 그림을 보자.

 

 

정사각형의 최대 넓이는 이전 정사각형 정보들을 토대로 충분히 유추 가능하다. 본 예시에서 dp[i-1][j-1] = 3, dp[i-1][j] = 2, dp[i][j-1] = 5이다. 이 정사각형 내부의 모든 사각형들은 위 조건 (전부 2종류의 과일로 이루어짐)을 만족한다.

여기서 dp[i][j]를 포함한 조건을 만족시키는 정사각형을 새로 그리려고 할 때, 우리는 직관적으로 그 변의 길이가 3임을 알 수 있다.

 

 

더 잘 생각해보면, dp[i-1][j-1]은 대각선, dp[i][j-1]은 가로, dp[i-1][j]는 세로 방향으로 조건을 만족시킴을 보장한다. 조건을 만족하는 정사각형을 형성하려면 세 방향 모두 조건을 만족시켜야 한다. 즉 셋 중 가장 최솟값에 1을 더한 값이 새로운 dp[i][j]값이 된다. 식으로 나타내면 다음과 같다.

 

dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1

 

 

참고로, 좌표 (i, j)가 조건을 만족할 때를 전제로 하니, 만약 좌표가 조건을 만족하지 않는다면(초기화했을 때 dp[i][j]가 0이라면) 바로 넘어가면 된다.

 

 

 

풀이 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

farm_maps = [[0]*N for _ in range(N)]

for _ in range(M) :
  X, Y, L, F = map(int, input().split())
  for i in range(Y, Y+L) :
    for j in range(X, X+L) :
      farm_maps[i][j] = F


def search(target1, target2) :
  dp = [[0]*N for _ in range(N)]

  for i in range(N) :
    for j in range(N) :
      if farm_maps[i][j] == target1 or farm_maps[i][j] == target2 :
        dp[i][j] = 1

  for i in range(1, N) :
    for j in range(1, N) :
      if not dp[i][j] : 
        continue
      dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
  return max(map(max, dp))

result = 0  
for i in range(1, 8) :
  for j in range(i+1, 8) :
    result = max(result, search(i, j))

print(result**2)

풀이 완료!