Ray`s Tech Lab

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

1. 브루트 포스로 접근한다면

첫 번째 열부터 마지막 열까지 채운다고 할 때 

지금 열을 세로블록으로 채울지

지금 열 + 바로다음열을 가로블록 2개로 채울지

를 선택함

러~프하게 생각하면 2^N개정도의 경우가 나오고 N은 최대 1000까지 주어지니 이 방법은 못 쓴다.

2. DP로 접근

k번째 열까지 채우는 것은

1) k - 2번째 열까지 채우고 세로블록 두 개 연달아 놓거나 가로블록 찍찍 놓거나

2) k - 1번째 열까지 채우고 세로블록 하나 놓거나

이 방법이다. 

나는 여기서 k - 2번째 열까지 채우고 세로블록 두 개를 연달아 놓는 것과 k - 1번째 열까지 채우고 세로블록을 하나 놓는 것은 중복되는 것이 있으므로 그 부분을 처리하기 위해 공을 들였는데, 다 풀고 보니 예외처리할 필요가 없었다. 

k - 2번째 열까지 채우고 세로블록을 두 개 연달아 놓는 행위가 k - 1번째 열까지 채우고 세로블록 하나 놓는 행위에 포함되기 때문. 

k - 2번째 열까지 채우고 세로블록을 두 개 놓는 것을 동시에 놓는 게 아니라 하나하나 놓는다고 해보면, k - 2번째 열까지 채우고 세로블록을 하나 낳고 그 다음에 하나를 마저 놓는 것이지만 처음에 하나를 놓는 과정에서 이미 k - 1번째 열까지 채운 것이 된다는 것이다.

즉 k - 2번재 열까지 채우고 k번째 열까지 채우는 과정은 가로블록을 찍찍 놓는것만 생각하면 되는 것이었다.

일단 아쉬운 대로 내 풀이 공유..

N = int(input())

MOD = 10007
# dp[x][0] : x번째 열까지 채우는데 마지막이 세로로 끝나는 경우
# dp[x][1] : x번째 열까지 채우는데 마지막이 가로로 끝나는 경우
dp = [[0, 0], [1, 0], [1, 1], [2, 1]]

for i in range(4, 1001):
    dp.append(
        [(sum(dp[i - 2]) + dp[i - 1][1]) % MOD, sum(dp[i - 2]) % MOD]
    )

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

더 나은 풀이

N = int(input())

MOD = 10007

dp = [0, 1, 2, 3]

for i in range(4, N + 1):
    dp.append((dp[i - 2] + dp[i - 1]) % MOD)

print(dp[N])

느낀점

일단 이런 DP문제를 점화식을 세우는 과정에서 앗? 중복되니까 예외처리할 부분이 있는데? 라고 생각되는 부분들이 있다. k - 2번째와 k - 1번째에 어떤 연산?을 해주어 k번째를 구하는 경우, k - 2번째에서 구하는 것과 k - 1번째에서 구하는 것들이 새로 중복되는 게 있는 거 같은데? 하는. 그러나 k - 2번째에서 특정 연산을 하는 것을 유심히 보며 중간에 k - 1번째가 '되는' 부분이 있는지 봐야할 것이다. 그렇다면 그 부분을 빼고 생각하면 중복처리 땜에 머리 굴릴 필요가 없어지니까. 애시당초 k - 2번째와 k - 1번째에 서로 다른 종류의 연산을 가미해 중복될 일이 없도록 처음부터 생각하는 것도 방법일 듯하다.

그리고 굳이 처음부터 어떤 관계가 있을까 하며 뇌피셜로 점화식 세울라 하지 말고, 일단 2번째일땐 이 만큼의 가짓수, 3번째일땐 이만큼의 가짓수, 4번째일땐 이만큼의 가짓수..하면서 쭉 쓰다가 점화식 관계를 발견하는 것도 하나의 방법일 듯하다. 하나의 틀에 박히지 말자.

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

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

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

이 문제를 무식하게 모든 경우의 수를 따져서 풀려고 하면 어떻게 할 수 있을까? 각 열에서 하나의 스티커만 뽑을 수 있으므로 최대 n개의 스티커를 뽑을 수 있다. 즉 각 열에 대해 위의 스티커를 뽑던가, 아래의 스티커를 뽑던가, 안 뽑던가의 3가지 갈래가 있고 n열까지 있으니 3^n개의 조합들이 나오고, 여기서 변을 공유하는 스티커를 뽑은 케이스를 쳐내야한다. 즉 이 방법의 시간복잡도는 O(3^n)정도가 될 것이고 n은 문제에서 최대 100,000으로 주어진다 했으니 연산횟수는 천문학적인(?) 숫자가 된다. 주어진 시간제한 1초 내에 이 방법으로 문제를 푸는 것은 매우 힘들다..고 봐야 한다.

그럼 어떻게 접근할 수 있는가. 그리디하게 접근한다면 일단 각 열에서 무조건 스티커를 떼는데, 가장 높은 값의 스티커들만 떼가야 한다. 그러나 당연히 이는 불가능하다. 변을 공유하는 스티커를 뗄 수 없으니 1번째 열의 스티커를 떼면 그 다음 열에서 뗄 수 있는 스티커, 또 그 다음 열에서 뗄 수 있는 스티커가 정해진다. 이 방법은 최적의 답을 도출할 수 없다.

이번엔 dp를 의심해보자. 일단 이 문제는 부분 문제로 쪼갤 수 있다. 1번째 열부터 차례차례 스티커를 떼고 n번째 열의 스티커를 뗀다고 해보자. 물론 각 열의 스티커는 안 뗄 수도 있다. 이 때 정답은 가장 큰 점수를 얻는 스티커 조합이므로, 위쪽 스티커든 아래쪽 스티커든 간에 n번째 열의 스티커는 떼야 한다. 그렇다면 답은

마지막 스티커(n번째 열)을 위쪽을 뽑은 경우

마지막 스티커(n번째 열)을 아래쪽을 뽑은 경우

이 둘 중 하나다. 여기서 단순히 n번째 열 스티커를 위쪽을 뽑았다면, 이 점수를 n - 1번째 스티커를 아래쪽을 뽑은 경우에 나오는 값에 더해야 합니다. 라고 하면 안된다.  다음 예시를 보자

1 ~ 3열까지 스티커를 뽑았을 때 나오는 최대 점수는 몇인가? 라는 문제라면 1, 2열에서 뭘 뽑던 3열에서 스티커 하나를 뽑은 케이스가 정답이 된다. 3열에서 아래쪽을 뽑은 케이스를 알기 위해 2열에서 위쪽을 뽑은 케이스를 더한다면 이 때 구해지는 점수는 2 + 2 + 25 = 29가 된다. 그러나 3열에서 아래쪽을 뽑은 케이스의 최대값은 35다! 1열에서 10을, 2열에서 아무것도 안 뽑고 3열에서 25를 뽑은 케이스. 즉, n번째 열의 위쪽을 뽑은 경우 얻는 점수의 최대는

n - 1번째 스티커를 아래쪽을 뽑은 경우의 최대누적합

n - 2번째 스티커를 뽑은 경우(위, 아래 상관없음)의 최대누적합

이 둘 중 더 큰 값에 n번째 열의 위쪽스티커의 점수를 합한 것이다. dp[1][i]이 i번째 열에서 위쪽 스티커를 뽑은 경우의 최대누적합, dp[2][i]가 i번째 열에서 아래쪽 스티커를 뽑은 경우의 최대누적합이라 하면 점화식은 다음과 같이 얻어진다.

dp[1][n] = max(dp[2][n-1], max(dp[1][n-2], dp[2][n-2]))

dp[2][n] = max(dp[1][n-1], max(dp[1][n-2], dp[2][n-2]))

이걸 고대로 코드로 옮기면 된다.

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    n = int(sys.stdin.readline())
    sticker = [[0]]
    sticker.append([0] + list(map(int, sys.stdin.readline().split())))
    sticker.append([0] + list(map(int, sys.stdin.readline().split())))

    dp = [[0 for i in range(n + 1)] for j in range(3)]
    dp[1][1] = sticker[1][1]
    dp[2][1] = sticker[2][1]

    for i in range(2, n + 1):
        dp[1][i] = max(dp[2][i - 1], max(dp[1][i - 2], dp[2][i - 2])) + sticker[1][i]
        dp[2][i] = max(dp[1][i - 1], max(dp[1][i - 2], dp[2][i - 2])) + sticker[2][i]

    print(max(dp[1][n], dp[2][n]))