https://www.acmicpc.net/problem/25589
| 시간 제한 | 메모리 제한 |
| 1초 | 1024MB |
문제
N*N 크기의 격자 위에 칸마다 코인이 놓여있다.
푸앙이는 격자 위에 한 변의 길이가 1 이상 N이하인 정사각형 그물을 만들어 그 안의 코인을 얻을 수 있다. 하지만 그물이 포함하는 칸 개수의 제곱에 해당하는 코인을 지불해야 한다.
그물은 반드시 N*N크기의 격자 안에 완전히 포함 되어야 하고, 한 번 그물을 친 칸에는 다시 그물을 칠 수 없다.
푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 구하시오.
입력
첫 번째 줄에 정수 N(2 ≤ N ≤ 400)이 주어진다.
두 번째 줄부터 N개의 줄에는 칸에 놓여 있는 코인의 수가 1행부터 차례대로 주어진다. 칸에 놓여 있는 코인의 수는 10^9 이하의 양의 정수이다.
출력
첫 번째 줄에 푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 출력한다.
풀이
N의 범위가 400으로 매우 만만해 보입니다. 최대 크기의 격자인 400*400에 그물을 한 번 치는 경우의 수를 생각해 봅시다. 400*400으로 1가지, 399*399로 2*2가지, 398*398로 3*3가지,... 1*1로 400*400가지, 모두 더해보면 21,413,400가지입니다. 시도해 볼 만한 숫자이지만 그물을 두 번 쳐야 한다는 점이 문제입니다. 2천만 가지의 경우로 그물을 한 번 쳤을 때, 나머지 그물을 치는 경우를 모두 구해보면 경우의 수가 너무 커집니다.
문제에서 주어진 세 가지 조건을 봅시다. "한 변의 길이가 1이상 N이하인 정사각형 그물", "그물은 반드시 N*N크기의 격자 안에 완전히 포함", "한 번 그물을 친 칸에는 다시 그물을 칠 수 없다." 이 세 조건에 맞게 그물을 친다면 그물의 배치는 이런 특징을 갖게 됩니다.
두 개의 그물은 반드시 전체 격자를 상하, 또는 좌우로 분할한 두 개의 직사각형 안에 따로 포함됩니다. 이걸 두고 보면 전체 격자를 이렇게 분할해 볼 수 있습니다.
격자를 a, c와 b, d로 상하 분할하는 지점을 i로, a, b와 c, d로 좌우 분할하는 지점을 j라고 합시다. 이제 이 안에 두 개의 그물을 배치한다면 다음 두 가지 경우만 가능합니다.
- a, c에 하나의 그물을 배치하고 b, d에 나머지 하나를 배치
- a, b에 하나의 그물을 배치하고 c, d에 나머지 하나를 배치
각각의 그물이 어디에 어떻게 있어야 하는가를 따로 구한다면 앞서 말했듯이 시간초과입니다. 하지만 a, b 직사각형에서 만들어지는 가장 좋은 그물의 정보가 이미 있다면 400개의 i와 400개의 j에 대해 O(400*400)의 시간 안에 가장 좋은 두 개의 그물을 찾아낼 수 있습니다. 그 전에 전체 격자를 상하 또는 좌우로 나누어 분할했을 때 분할 된 직사각형 안에서 만들 수 있는 가장 좋은 그물로 얻는 코인의 양을 다음 배열로 관리합니다.
left[i] = i번째 칸을 기준으로 왼쪽 직사각형에서 얻는 최적해
right[i] = i번째 칸을 기준으로 오른쪽 직사각형에서 얻는 최적해
up[j] = j번째 칸을 기준으로 위쪽 직사각형에서 얻는 최적해
down[j] = j번째 칸을 기준으로 아래쪽 직사각형에서 얻는 최적해
그럼 i를 기준으로 좌우 분할한다면 left[i]와 right[i + 1]로 가장 좋은 두 개의 그물을 찾을 수 있습니다. 상하 분할한다면 up[i], down[i + 1]입니다.
왼쪽 윗 칸이 a + 1, b + 1로 시작되고 한 변의 길이가 k인 정사각형의 그물을 생각해 봅시다.
주황색 영역에 친 그물로 얻는 코인을 coin(a, b, k)라고 하겠습니다. 왼쪽 위 끝 칸이 a, b가 아닌 이유는 이게 점이 아니라 칸이기 때문입니다. a+1로 시작해야 a+k가 k번째 칸이 됩니다. 그럼 이 그물로 인해 전체 격자는 4가지 방법으로 분할되고, 그물이 포함되는 배열은 이렇습니다.
1) 그물의 왼쪽변으로 좌우 분할, 그물은 right[b + 1]에 포함
2) 그물의 오른쪽변으로 좌우 분할, 그물은 left[b + k]에 포함
3) 그물의 윗변으로 상하 분할, 그물은 down[a + 1]에 포함
4) 그물의 아랫변으로 상하 분할, 그물은, up[a + k]에 포함
그럼 이제 대강 2천만 가지의 그물을 모두 만들어보며 left, right, up, down 배열의 최적해를 각각 정리하고 400*400가지의 분할 지점에 따라 좌우, 상하 직사각형의 두 그물을 확인해보면 O(N^3)으로 가장 좋은 두 개의 그물을 찾을 수 있습니다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
n = int(input())
coins = [list(map(int, input().split())) for _ in range(n)]
quad = [i ** 4 for i in range(400)]
# 그물로 얻는 코인을 확인
def net(a, b, k):
ret = -quad[k]
ret += coins[a + k][b + k]
if a >= 0 : ret -= coins[a][b + k]
if b >= 0: ret -= coins[a + k][b]
if a >= 0 and b >= 0 : ret += coins[a][b]
return ret
# 좌, 우, 상, 하의 최적 그물을 관리할 배열
l = [0] * n
r = [0] * n
u = [0] * n
d = [0] * n
# 격자의 누적합 생성
for i in range(n):
for j in range(1, n):
coins[i][j] += coins[i][j - 1]
for j in range(n):
for i in range(1, n):
coins[i][j] += coins[i - 1][j]
# 가능한 모든 그물로 분할 영역의 최적해 구하기
for k in range(1, 400):
for i in range(-1, n - k):
for j in range(-1, n - k):
sq = net(i, j, k)
u[i + k] = max(u[i + k], sq)
d[i + 1] = max(d[i + 1], sq)
l[j + k] = max(l[j + k], sq)
r[j + 1] = max(r[j + 1], sq)
for i in range(1, n):
if l[i] < l[i - 1]: l[i] = l[i - 1]
if u[i] < u[i - 1]: u[i] = u[i - 1]
for i in range(n - 2, -1, -1):
if r[i] < r[i + 1]: r[i] = r[i + 1]
if d[i] < d[i + 1]: d[i] = d[i + 1]
# 모든 칸을 기준으로 상하 또는 좌우 분리된
# 두 직사각형에서 최적해 탐색
res = 0
for i in range(1, n):
if l[i - 1] + r[i] > res:
res = l[i - 1] + r[i]
if u[i - 1] + d[i] > res:
res = u[i - 1] + d[i]
print(res)
solution()
https://www.acmicpc.net/problem/25589
| 시간 제한 | 메모리 제한 |
| 1초 | 1024MB |
문제
N*N 크기의 격자 위에 칸마다 코인이 놓여있다.
푸앙이는 격자 위에 한 변의 길이가 1 이상 N이하인 정사각형 그물을 만들어 그 안의 코인을 얻을 수 있다. 하지만 그물이 포함하는 칸 개수의 제곱에 해당하는 코인을 지불해야 한다.
그물은 반드시 N*N크기의 격자 안에 완전히 포함 되어야 하고, 한 번 그물을 친 칸에는 다시 그물을 칠 수 없다.
푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 구하시오.
입력
첫 번째 줄에 정수 N(2 ≤ N ≤ 400)이 주어진다.
두 번째 줄부터 N개의 줄에는 칸에 놓여 있는 코인의 수가 1행부터 차례대로 주어진다. 칸에 놓여 있는 코인의 수는 10^9 이하의 양의 정수이다.
출력
첫 번째 줄에 푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 출력한다.
풀이
N의 범위가 400으로 매우 만만해 보입니다. 최대 크기의 격자인 400*400에 그물을 한 번 치는 경우의 수를 생각해 봅시다. 400*400으로 1가지, 399*399로 2*2가지, 398*398로 3*3가지,... 1*1로 400*400가지, 모두 더해보면 21,413,400가지입니다. 시도해 볼 만한 숫자이지만 그물을 두 번 쳐야 한다는 점이 문제입니다. 2천만 가지의 경우로 그물을 한 번 쳤을 때, 나머지 그물을 치는 경우를 모두 구해보면 경우의 수가 너무 커집니다.
문제에서 주어진 세 가지 조건을 봅시다. "한 변의 길이가 1이상 N이하인 정사각형 그물", "그물은 반드시 N*N크기의 격자 안에 완전히 포함", "한 번 그물을 친 칸에는 다시 그물을 칠 수 없다." 이 세 조건에 맞게 그물을 친다면 그물의 배치는 이런 특징을 갖게 됩니다.
두 개의 그물은 반드시 전체 격자를 상하, 또는 좌우로 분할한 두 개의 직사각형 안에 따로 포함됩니다. 이걸 두고 보면 전체 격자를 이렇게 분할해 볼 수 있습니다.
격자를 a, c와 b, d로 상하 분할하는 지점을 i로, a, b와 c, d로 좌우 분할하는 지점을 j라고 합시다. 이제 이 안에 두 개의 그물을 배치한다면 다음 두 가지 경우만 가능합니다.
- a, c에 하나의 그물을 배치하고 b, d에 나머지 하나를 배치
- a, b에 하나의 그물을 배치하고 c, d에 나머지 하나를 배치
각각의 그물이 어디에 어떻게 있어야 하는가를 따로 구한다면 앞서 말했듯이 시간초과입니다. 하지만 a, b 직사각형에서 만들어지는 가장 좋은 그물의 정보가 이미 있다면 400개의 i와 400개의 j에 대해 O(400*400)의 시간 안에 가장 좋은 두 개의 그물을 찾아낼 수 있습니다. 그 전에 전체 격자를 상하 또는 좌우로 나누어 분할했을 때 분할 된 직사각형 안에서 만들 수 있는 가장 좋은 그물로 얻는 코인의 양을 다음 배열로 관리합니다.
left[i] = i번째 칸을 기준으로 왼쪽 직사각형에서 얻는 최적해
right[i] = i번째 칸을 기준으로 오른쪽 직사각형에서 얻는 최적해
up[j] = j번째 칸을 기준으로 위쪽 직사각형에서 얻는 최적해
down[j] = j번째 칸을 기준으로 아래쪽 직사각형에서 얻는 최적해
그럼 i를 기준으로 좌우 분할한다면 left[i]와 right[i + 1]로 가장 좋은 두 개의 그물을 찾을 수 있습니다. 상하 분할한다면 up[i], down[i + 1]입니다.
왼쪽 윗 칸이 a + 1, b + 1로 시작되고 한 변의 길이가 k인 정사각형의 그물을 생각해 봅시다.
주황색 영역에 친 그물로 얻는 코인을 coin(a, b, k)라고 하겠습니다. 왼쪽 위 끝 칸이 a, b가 아닌 이유는 이게 점이 아니라 칸이기 때문입니다. a+1로 시작해야 a+k가 k번째 칸이 됩니다. 그럼 이 그물로 인해 전체 격자는 4가지 방법으로 분할되고, 그물이 포함되는 배열은 이렇습니다.
1) 그물의 왼쪽변으로 좌우 분할, 그물은 right[b + 1]에 포함
2) 그물의 오른쪽변으로 좌우 분할, 그물은 left[b + k]에 포함
3) 그물의 윗변으로 상하 분할, 그물은 down[a + 1]에 포함
4) 그물의 아랫변으로 상하 분할, 그물은, up[a + k]에 포함
그럼 이제 대강 2천만 가지의 그물을 모두 만들어보며 left, right, up, down 배열의 최적해를 각각 정리하고 400*400가지의 분할 지점에 따라 좌우, 상하 직사각형의 두 그물을 확인해보면 O(N^3)으로 가장 좋은 두 개의 그물을 찾을 수 있습니다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
n = int(input())
coins = [list(map(int, input().split())) for _ in range(n)]
quad = [i ** 4 for i in range(400)]
# 그물로 얻는 코인을 확인
def net(a, b, k):
ret = -quad[k]
ret += coins[a + k][b + k]
if a >= 0 : ret -= coins[a][b + k]
if b >= 0: ret -= coins[a + k][b]
if a >= 0 and b >= 0 : ret += coins[a][b]
return ret
# 좌, 우, 상, 하의 최적 그물을 관리할 배열
l = [0] * n
r = [0] * n
u = [0] * n
d = [0] * n
# 격자의 누적합 생성
for i in range(n):
for j in range(1, n):
coins[i][j] += coins[i][j - 1]
for j in range(n):
for i in range(1, n):
coins[i][j] += coins[i - 1][j]
# 가능한 모든 그물로 분할 영역의 최적해 구하기
for k in range(1, 400):
for i in range(-1, n - k):
for j in range(-1, n - k):
sq = net(i, j, k)
u[i + k] = max(u[i + k], sq)
d[i + 1] = max(d[i + 1], sq)
l[j + k] = max(l[j + k], sq)
r[j + 1] = max(r[j + 1], sq)
for i in range(1, n):
if l[i] < l[i - 1]: l[i] = l[i - 1]
if u[i] < u[i - 1]: u[i] = u[i - 1]
for i in range(n - 2, -1, -1):
if r[i] < r[i + 1]: r[i] = r[i + 1]
if d[i] < d[i + 1]: d[i] = d[i + 1]
# 모든 칸을 기준으로 상하 또는 좌우 분리된
# 두 직사각형에서 최적해 탐색
res = 0
for i in range(1, n):
if l[i - 1] + r[i] > res:
res = l[i - 1] + r[i]
if u[i - 1] + d[i] > res:
res = u[i - 1] + d[i]
print(res)
solution()
