[BOJ] 1915 - 가장 큰 정사각형 (Python) / 데이터 추가

 

 

아이디어

 

동적 계획법으로 각 칸에서 만들 수 있는 정사각형 한 변의 크기를 저장해 나간다.

 

 

풀이 #1

 

리스트 dp에 배열 첫 줄을 입력 받고, 결과값을 저장하는 변수 res에 배열 첫 줄에서 가장 큰 값을 저장한다.

 

for문에서 arr에 배열을 한 줄씩 입력 받고, 차례로 arr에서 1로 된 칸들에 왼쪽 칸, 위쪽 칸, 좌상단 칸 중 최솟값을 더한다.

위쪽 칸과 현재 칸은 각각 다음 칸에서 좌상단 칸과 왼쪽 칸이 되므로 하나라도 0인 경우 두 칸을 건너뛰도록 한다.

 

res를 현재 줄의 최댓값과 비교해 갱신하고, 다음 for문을 위해 dp를 arr로 대체한다.

res는 정사각형 한 변의 길이를 나타내므로 마지막에 res를 제곱하여 출력한다.

 

import sys

input = sys.stdin.readline

def solution():
    n, m = map(int, input().split())
    dp = list(map(int, [*input().rstrip()]))
    res = max(dp)
    for _ in range(n-1):
        arr = list(map(int, [*input().rstrip()]))
        i = 1
        while i < m:
            if dp[i] == 0:
                i += 1
            elif arr[i] == 0:
                i += 1
            elif dp[i-1] and arr[i-1]:
                arr[i] += min(dp[i-1], dp[i], arr[i-1])
            i += 1
        res = max(res, max(arr))
        dp = arr
    print(res**2)

solution()

 

 

 

풀이 #2

 

다른 분의 코드를 참고하여 따라해보았다.

 

for문에서 arr에 배열을 한 줄씩 입력 받고, dp에는 각 칸까지 세로로 1이 연속되는 길이를 저장해 나간다.

세로로 1이 연속되는 길이가 결과값 res보다 더 크면 temp를 1 증가시켜 세로와 가로 모두 1이 연속되는 길이를 저장한다.

temp가 res보다 더 크면 res를 1 증가시킨 후 temp를 다시 0으로 되돌려 길이를 다시 재도록 한다.

 

import sys

input = sys.stdin.readline

def solution():
    n, m = map(int, input().split())
    dp = list(map(int, [*input().rstrip()]))
    res = max(dp)
    for _ in range(n-1):
        arr = list(map(int, [*input().rstrip()]))
        temp = 0
        for i in range(m):
            if arr[i] == 0:
                dp[i] = 0
                continue
            dp[i] += arr[i]
            if dp[i] > res:
                temp += 1
                if temp > res:
                    res += 1
                    temp = 0
            else:
                temp = 0
    print(res**2)

solution()

 

 

 

풀이 #3 (틀린 코드)

 

다른 분의 코드를 참고하여 따라하여 통과되긴 했으나, 반례가 존재하는 것을 발견했다.

풀이 #2의 코드에서 res를 1 증가시키는 if문에서 temp를 0으로 되돌리지 않는다.

 

import sys

input = sys.stdin.readline

def solution():
    n, m = map(int, input().split())
    dp = list(map(int, [*input().rstrip()]))
    res = max(dp)
    for _ in range(n-1):
        arr = list(map(int, [*input().rstrip()]))
        temp = 0
        for i in range(m):
            if arr[i] == 0:
                dp[i] = 0
                continue
            dp[i] += arr[i]
            if dp[i] > res:
                temp += 1
                if temp > res:
                    res += 1
            else:
                temp = 0
    print(res**2)

solution()

 

 

같은 방식으로 행과 열을 전치하여 처리하는 코드는 틀렸다고 나왔다.

# 틀린 코드
arr = [list(map(int, [*input().rstrip()])) for _ in range(n)]
dp = [0]*n
res = 0
for j in range(m):
    temp = 0
    for i in range(n):
        if arr[i][j] == 0:
            dp[i] = 0
            continue
        dp[i] += arr[i][j]

 

 

반례

 

Input:
3 6
000100
011110
011111

Output: 9
Answer: 4


Input:
4 5
00001
01111
01111
01111

Output: 16
Answer: 9


Input:
5 7
0000001
0000011
0011111
0111111
0111111

Output: 25
Answer: 9


Input:
6 7
0000101
0111111
0111111
0111111
0111111
0111111

Output: 36
Answer: 25

 

이에 따라 BOJ에 데이터 추가를 요청했다.

 

 

재채점 전

 

 

 

 

재채점 후

 

 

 

 

 

 

반례를 찾고 데이터를 추가하는 일이 막연하게 쉽지 않겠다고만 생각했는데 이렇게 기여할 수 있어 뿌듯했다.