Ray`s Tech Lab

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

주어진 정사각형 모양의 표에서 좌표 2개로 주어지는 특정 영역의 합을 구하는 문제.

(x1, y1)과 (x2, y2)로 주어지는 두 좌표에 대해 x1 <= x2, y1 <= y2가 성립하며 표는 최대 1024 * 1024사이즈이고 최대 100,000번의 합을 구해야 한다.

무식하게 즉 브루트한 방법으로 푼다면 M번의 트라이에 대해 그 때마다 반복문을 돌며 처리할 수 있다. 그러나 이 방법으로 한다면 최악의 경우 100,000 * 1024 * 1024번의 연산을 해야 하며, 주어진 시간인 1초 내에 통과할 수 없을 것이다.

매번 새로 합을 구하는 것이 아니라 이전에 구한 값을 재활용하는 DP를 통해 문제에 접근해야 한다는 생각이 들었다. 그러나 K번째 트라이에 대한 답을 구할 때 이전 트라이에서 구한 답을 이용해 구할 수 있을지는..

그러다가 풀이방법이 떠올랐다. 누적합을 이용하는 것이다. sum[r][c]가 (0, 0)에서 (r, c)까지의 영역의 합을 의미한다고 하고 (0, 0)부터 (N, N)까지의 모든 sum값을 구해뒀다고 하자. 그렇다면 이를 활용해 임의의 두 좌표 (x1, y1)부터 (x2, y2)의 영역의 합을 sum값을 이리저리 활용해 구할 수 있다! 이 sum값을 구할 때 내가 생각한 방법은

sum[r][c] = sum[r - 1][c] + r번째 행에서 1번 ~ c번값까지의 누적합 이었지만, 다른 사람들의 풀이를 보니

sum[r][c] = sum[r - 1][c] + sum[r][c - 1] - sum[r - 1][c - 1] + r번째 행에서 c번값

으로도 할 수 있고, 이게 더 쉬운 듯.

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

dp = [[0 for i in range(N + 1)] for j in range(N + 1)]

for r in range(1, N + 1):
    new_line = [0] + list(map(int, input().split()))
    accumalated_sum = 0
    for c in range(1, N + 1):
        accumalated_sum += new_line[c]
        dp[r][c] = dp[r - 1][c] + accumalated_sum

for _ in range(M):
    r1, c1, r2, c2 = map(int, input().split())
    answer = (
        dp[r2][c2] -
        dp[r1 - 1][c2] -
        (dp[r2][c1 - 1] - dp[r1 - 1][c1 - 1])
    )
    print(answer)

이 경우 시간복잡도는 O(N*2)이며 시간 내 통과가능!

dp는 정말 배울 게 많다는 점을 느끼게 해준 문제. 누적합 관련된 문제에서도 충분히 DP가 쓰일 수 있다. 또한 문제에 쓰일 재료(여기선 누적합들을 재료로 특정 구간의 합을 도출)를 만드는데에 DP방식이 쓰일 수 있음을 알게 됐다. 더욱 더 열심히 하자..

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

0마리를 배치하는 것도 가능하고, 가로 세로로 붙지 않도록 배치해야 하므로 이론상 N마리까지 배치가능하다.

1. 브루트한 방법으로 풀이

직접 0 ~ N마리의 사자들을 하나하나 배치하는 방법이 있는데, 이 방법은 러프하게 생각하면 2^2n번 정도의 연산을 하게 될텐데 n은 100,000까지 주어질 수 있으므로 시간 내에 통과할 수 없을 것이다.

그렇다면 DP나 그리디를 통한 방법을 의심헤야 한다.

2. 우선 부분문제로 쪼갤 수 있는가?

쪼갤 수 있다. K마리(K <= N)의 사자를 배치한다고 할 때

1) 첫 사자를 첫째 줄 왼쪽 칸에 배치하는 경우

2) 첫 사자를 첫째 줄 오른쪽 칸에 배치하는 경우

3) 첫 사자를 첫째 줄에 배치하지 않는 경우

로 쪼갤 수 있다.

3. 그럼 중복되는 구조가 있는가? 있다면 DP로 풀이가 가능할 것이다.

중복되는 구조 역시 있다. N개의 행에 사자 K마리를 배치한다 할 때

첫 사자를 첫 줄 왼쪽에 배치할 땐 두 번째 사자를 다음 줄의 오른쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

첫 사자를 첫 줄 오른쪽에 배치할 땐 두 번째 사자를 다음 줄의 왼쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

첫 사자를 첫 줄에 배치하지 않을 땐 두 번째 사자를 그 줄의 왼쪽 또는 오른쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

정리하자면

f(N, K, left)를 N개의 행에 사자 K마리를 배치하는데 첫 줄 왼쪽에 사자를 두는 경우

f(N, K, right)를 N개의 행에 사자 K마리를 배치하는데 첫 줄 오른쪽에 사자를 두는 경우

f(N, K, no)를 N개의 행에 사자 K마리를 배치하는데 첫 줄에 사자를 두지 않는 경우라고 한다면

f(N, K, left) = f(N-1, K-1, right) + f(N-1, K-1, no)f(N, K, right) = f(N-1, K-1, left) + f(N-1, K-1, no)f(N, K, no) = f(N-1, K, left) + f(N-1, K, right) + f(N-1, K, no)이라는 관계를 구할 수 있고, 중복되는 케이스들을 관찰가능하다.

4. 점화식을 세워보자

사실 점화식은 위에서 이미 세웠다. dp[i][j][k]라는 배열을 만들어서 그대로 적용라면 되며, 최종적으론 dp[N][0] ~ dp[N][N]까지를 합치면 그것이 답이 될 것이다.그러나 문제가 있다. 저 식 그대로 DP배열을 만들어서 사용하자면 3차원 배열이 만들어지는데, N은 최대 10만이고 K도 N까지의 범위를 가지니 10만 X 10만 X 3 = 3백억의 크기를 갖는 배열이 만들어지고 이는 메모리 제한에 걸릴 것이다..여기서 막혔고, 많은 고민을 하다가 다른 분들이 푼 걸 참고하게 됐다..

위의 점화식은 "몇 마리의 사자를 배치하는가"에도 중점이 있는 점화식이며, 첫 줄의 왼쪽에 배치하는 경우와 오른쪽에 배치하는 경우 그리고 첫 줄에 배치를 하지 않는 경우라는 3가지 케이스로 쪼개어 경우의 수들을 관리한다. 그러나 X개의 행에서 K마리의 사자를 배치하는 여러 방법들이 있다고 할 때, 행의 수 X만 같다면 그 방법들 모두 한꺼번에 묶어서 첫 줄의 왼쪽/오른쪽에 배치하는 경우와 첫 줄에 배치하지 않는 경우라는 3가지 케이스로 분류할 수 있다. 행의 수만 같다면 마리 별로 배치하는 방법까진 고려하지 않아도 되는 것.

즉 dp[x]를 x개의 행(즉 2*x칸의 우리)에 사자들을 배치하는 방법이라 하면, dp[x] = dp[x][left] + dp[x][right] + dp[x][no]라는 3가지 케이스로 보는 게 더 편하다는 것임 

이렇게하면 점화식이 훨씬 쉬워진다.

dp[N][left] = dp[N-1][right] + dp[N-1][no]

dp[N][right] = dp[N-1][left] + dp[N-1][no]

dp[N][no] = dp[N-1][left] + dp[N-1][right] +dp[N-1][no]

N = int(input())

mod = 9901

dp = [[0, 0, 0] for _ in range(N + 1)]
dp[1] = [1, 1, 1]

for i in range(2, N + 1):
    dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % mod
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod
    dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod

print(sum(dp[N]) % mod)

느끼고, 배운 점

이 문제의 난이도가 실버1에 불과하단 걸 알고 현타가 왔다. 다른 사람들은 쉽게 생각하는 걸 나는 어렵게 생각했구나..라면서,, 

직관적으로 N=1일때의 배치방법, N=2일때의 배치방법들을 써가면서 규칙을 찾아 쉽게 푸는 방법도 있었다. 그래도 내가 한 방법이 잘못됐다고는 생각하지 않는다. 나만의 푸는 패턴을 만들어가며 연습하면서 감각을 길러가고, 실전에선 그 감각을 토대로 직관적으로(브루트하게 풀 수 있는지 없는지 따지고 그런 과정 없이) 풀 수 있을 거라고 생각한다..

배운 점은 글쎄..잘 모르겠다. 경험만이 살 길이란 생각이 들던 문제.