[백준알고리즘] 1451번: 직사각형으로 나누기 -Python

[백준알고리즘] 1451번: 직사각형으로 나누기 -Python

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

1451번: 직사각형으로 나누기

브루트 포스 방식으로 해결을 해야 한다. 애를 많이 먹고 다른 분들의 풀이를 살펴본 후 해결했다.

 

처음에 풀었던 방식으로는 각 테이블을 그룹 1, 2, 3으로 직접 나누었다. 이중 for문을 돌려가며 시작점을 설정하고, 그룹이 시작하는 좌표를 설정하고, 거기서부터 또다시 그룹이 끝나는 좌표를 설정했다. 마지막 3번째 그룹을 설정할 때에는 해당 시작 좌표에서 최대로 잡을 수 있는 크기를 잡아주었다. 그 후 합의 곱을 구하기 전에 모든 좌표가 그룹이 설정되었는지 확인하기를 반복했다.

이런 방식으로 해결을 하니 시간초과가 발생했다. 내가 푼 방식으로는 아무리 가지치기 혹은 중복을 줄이려고 애를 쓰더라도 모든 그룹을 칠하지 못하는 경우가 발생하기 때문에 그에 따른 낭비되는 시간이 많았다.

 

결국 다른 분들의 코드를 확인했고 백준님의 발표자료도 slide share에 올라가 있어서 개념을 참고했다.

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1451

 

이 방식은 주어진 테이블에서 3그룹으로 나눌 수 있는 모든 조건에 대해서만 검사를 수행한다. 따라서 내가 했던 방식처럼 모든 블록이 그룹에 속하지 않을 수도 있는 낭비되는 경우가 줄었다. 역시 브루트 포스도 어렵다..

 

 

문제를 통과한 후에는 다른 분들의 코드를 확인해봤는데 통과시간이 엄청 짧았던 코드들도 있었다. 지금은 머리아파서 못 볼 것 같지만 나중에 참고하면 좋을 것 같다.

import sys
 
n, m = map(int, sys.stdin.readline().split())
table = [list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(n)]
ans = 0
 
# |||
for i in range(1, m-1):
    for j in range(i+1, m):
        s1 = sum([table[a][b] for a in range(n) for b in range(i)])
        s2 = sum([table[a][b] for a in range(n) for b in range(i, j)])
        s3 = sum([table[a][b] for a in range(n) for b in range(j, m)])
        ans = max(ans, s1*s2*s3)
 
# ||
# --
for i in range(1, m):
    for j in range(1, n):
        s1 = sum([table[a][b] for a in range(j) for b in range(i)])
        s2 = sum([table[a][b] for a in range(j) for b in range(i, m)])
        s3 = sum([table[a][b] for a in range(j, n) for b in range(m)])
        ans = max(ans, s1*s2*s3)
 
# --
# ||
for i in range(1, n):
    for j in range(1, m):
        s1 = sum([table[a][b] for a in range(i) for b in range(m)])
        s2 = sum([table[a][b] for a in range(i, n) for b in range(j)])
        s3 = sum([table[a][b] for a in range(i, n) for b in range(j, m)])
        ans = max(ans, s1*s2*s3)
 
# =|
for i in range(1, n):
    for j in range(1, m):
        s1 = sum([table[a][b] for a in range(i) for b in range(j)])
        s2 = sum([table[a][b] for a in range(i, n) for b in range(j)])
        s3 = sum([table[a][b] for a in range(n) for b in range(j, m)])
        ans = max(ans, s1*s2*s3)
 
# |=
for i in range(1, n):
    for j in range(1, m):
        s1 = sum([table[a][b] for a in range(i) for b in range(j, m)])
        s2 = sum([table[a][b] for a in range(i, n) for b in range(j, m)])
        s3 = sum([table[a][b] for a in range(n) for b in range(j)])
        ans = max(ans, s1*s2*s3)
 
# -
# -
# -
for i in range(1, n-1):
    for j in range(i+1, n):
        s1 = sum([table[a][b] for a in range(i) for b in range(m)])
        s2 = sum([table[a][b] for a in range(i, j) for b in range(m)])
        s3 = sum([table[a][b] for a in range(j, n) for b in range(m)])
        ans = max(ans, s1*s2*s3)
 
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다