[백준] 14925번 목장 건설하기 _ Python

[초기 접근 방법]

어떻게 풀어야 될 지 감이 잡히지 않아,

O(N^4)으로 시간초과를 예상했지만 누적합도 복습할 겸

일단 누적합으로 제출했다.

 

누적합

→ https://www.acmicpc.net/source/66884805

→ https://nahwasa.com/entry/%EB%88%84%EC%A0%81-%ED%95%A9prefix-sum-2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9prefix-sum-of-matrix-with-java

 

 

[생각]

처음부터 dp를 고려해야 겠다는 생각을 못한 문제..

 

1. dp[i][j] : (i, j)에서 지을 수 있는 가장 큰 정사각형 목장 크기

 

2. 점화식

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

 

 

1)

처음에 dp[N-1][N-1]을 출력하는 코드로 작성했다.

하지만 (N-1, N-1) 좌표에 장애물이 있을 시, 해당 좌표의 dp 값은 갱신되지 않는다.

따라서 result 값으로 dp[i][j] 에서의 모든 값들 중 최댓값을 구하도록 하였다.

 

2)

Farm 전체가 장애물일 경우를 생각해서, result = -float('inf') 가 아닌 result = 0 으로 했어야 했다..

문제의 조건에 맞춰 자료구조(dp, graph), 변수(result) 값의 초기화에 항상 유의하자!!

 

 

 

[코드]

- 시간초과 코드 (누적합)

# 시간초과 날 것

# 풀이 시간 : 1시간 5분
# 시간복잡도 : O(n^4)
# 공간복잡도 : O(n^2)
# 참고 : https://www.acmicpc.net/source/66884805

# 누적합

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

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

# 해당 영역에 있는 숫자의 합을 구한다.
for i in range(1, M+1):
    for j in range(1, N+1):
        prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + farm[i-1][j-1]

result = -float('inf')
for a in range(1, M+1):
    for b in range(1, N+1):
        for c in range(M, a-1, -1):
            for d in range(N, b-1, -1):
                cal = prefixSum[c][d] - prefixSum[a][d] - prefixSum[c][b] + prefixSum[a][b]

                if cal == 0:
                    minLine = min(c-a, d-b) # 정사각형을 만들기 위해서는 작은변
                    result = max(result, minLine)

print(result)

 

 

- 정답 코드 (dp)

# 풀이 시간 : 1시간 5분 + 40분
# 시간복잡도 : O(MN)
# 공간복잡도 : O(MN)
# 참고 : https://www.acmicpc.net/source/66884805
#       https://sangdo913.tistory.com/116

import sys
input = sys.stdin.readline

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

# dp[i][j] : i, j 에서 지을 수 있는 가장 큰 정사각형 목장 크기
# dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
    # 왼쪽, 위쪽, 왼쪽 위 대각선
dp = [[0] * (N+1) for _ in range(M+1)]

result = 0
for i in range(1, M+1):
    for j in range(1, N+1):
        if farm[i-1][j-1] == 0:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            result = max(result, dp[i][j])

print(result)

 

 

 

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

14925번: 목장 건설하기