백준 1451번 직사각형으로 나누기

정보

문제 바로가기 [클릭]

난이도: Gold5

관련 개념: #누적합 #브루트포스 #많은 조건 분기

---

조건

시간 제한	메모리 제한
2 초	128 MB

---

문제

세준이는 NM크기로 직사각형에 수를 NM개 써놓았다.

세준이는 이 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누려고 한다. 각각의 칸은 단 하나의 작은 직사각형에 포함되어야 하고, 각각의 작은 직사각형은 적어도 하나의 숫자를 포함해야 한다.

어떤 작은 직사각형의 합은 그 속에 있는 수의 합이다. 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나누었을 때, 각각의 작은 직사각형의 합의 곱을 최대로 하는 프로그램을 작성하시오.

---

입력

첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 50보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다.

---

출력

세 개의 작은 직사각형의 합의 곱의 최댓값을 출력한다.

---

예제 입출력 1

입력

1 8
11911103

출력

108

---

예제 입출력 2

입력

3 3
123
456
789

출력

3264

---

예제 입출력 3

입력

3 1
7
9
3

출력

189

---

코드(파이썬)

n, m = map(int, input().split())
squares = [list(map(int, list(input()))) for _ in range(n)]
result = 0


# 6가지 형태 존재
# ││ / ㅏ / ㅓ
# =  / ㅗ / ㅜ
for i in range(1, m):
    left = sum([sum(line[:i]) for line in squares])
    for j in range(i+1, m):
        middle = sum([sum(line[i:j]) for line in squares])
        right = sum([sum(line[j:]) for line in squares])
        result = max(result, left*middle*right)
    for k in range(1, n):
        top = sum([sum(line[i:]) for line in squares[:k]])
        bottom = sum([sum(line[i:]) for line in squares[k:]])
        result = max(result, left*top*bottom)
for i in range(1, m):
    right = sum([sum(line[i:]) for line in squares])
    for k in range(1, n):
        top = sum([sum(line[:i]) for line in squares[:k]])
        bottom = sum([sum(line[:i]) for line in squares[k:]])
        result = max(result, right*top*bottom)
        
for i in range(1, n):
    top = sum([sum(line) for line in squares[:i]])
    for j in range(i+1, n):
        middle = sum([sum(line) for line in squares[i:j]])
        bottom = sum([sum(line) for line in squares[j:]])
        result = max(result, top*middle*bottom)
    for k in range(1, n):
        left = sum([sum(line[:k]) for line in squares[i:]])
        right = sum([sum(line[k:]) for line in squares[i:]])
        result = max(result, top*left*right)
for i in range(1, n):
    bottom = sum([sum(line) for line in squares[i:]])
    for k in range(1, m):
        left = sum([sum(line[:k]) for line in squares[:i]])
        right = sum([sum(line[k:]) for line in squares[:i]])
        result = max(result, bottom*left*right)
        
print(result)

---

특이사항

• 해결방법
  • 다익스트라를 이용
  • 현재 방문 도시까지의 경로를 path 리스트에 저장
  • 도착점에 도달하게 된다면 도착점까지의 경로를 출력
• 내 코드(30,840KB, 356ms)에 비해 우수한 코드(바로가기, 30,864KB, 80ms)와 비교

  • import sys
    
    N, M = map(int, sys.stdin.readline().split())
    cum = [[0]*(M+1) for _ in range(N+1)] # cumulative sum
    for i in range(1, N+1):
        for j, val in enumerate(map(int, sys.stdin.readline().rstrip()), 1):
            cum[i][j] = val + cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1]
    
    cardinal = 0
    for i in range(1, N):
        for j in range(1, M):
            up = cum[i][j] * (cum[i][M] - cum[i][j]) * (cum[N][M] - cum[i][M])
            down = cum[i][M] * (cum[N][j] - cum[i][j]) * (cum[N][M] - cum[i][M] - cum[N][j] + cum[i][j])
            left = cum[i][j] * (cum[N][j] - cum[i][j]) * (cum[N][M] - cum[N][j])
            right = cum[N][j] * (cum[i][M] - cum[i][j]) * (cum[N][M] - cum[i][M] - cum[N][j] + cum[i][j])
            cardinal = max(cardinal, up, down, left, right)
    horizontal = 0
    for i1 in range(1, N-1):
        for i2 in range(i1+1, N):
            horizontal = max(horizontal, cum[i1][M] * (cum[i2][M] - cum[i1][M]) * (cum[N][M] - cum[i2][M]))
    vertical = 0
    for j1 in range(1, M-1):
        for j2 in range(j1+1, M):
            vertical = max(vertical, cum[N][j1] * (cum[N][j2] - cum[N][j1]) * (cum[N][M] - cum[N][j2]))
    
    print(max(cardinal, horizontal, vertical))
    

  • 직사각형 넓이 계산
    • 기존: 반복문을 이용해 계산
    • 개선: cum 리스트에 넓이 저장

---

참고문헌

-