DP 문제입니다.
첫 번째 반복 단계에서 패턴을 찾으면 DP 문제를 빠르게 해결할 수 있습니다.
그리고 문제는 항상 찾을 수 없다는 것입니다 …
하지만 DP 문제를 풀면 풀수록 뇌가 DP가 되는 느낌이 든다.
나 같은 범재도 이렇게 반복하다보면 요령을 터득할 수 있을 것 같아 뿌듯했다.
※ 결국 노력과 반복만이 답이다…
- 문제 해결 아이디어 공유:
- 행 == 가로, 열 == 세로
- 먼저 각 행의 i번째까지 누적 합계를 저장하는 dp 목록을 만듭니다.
- 0으로 여백을 두는 것이 편리하기 때문에 인덱스 번호는 항상 1부터 시작하는 편입니다. 다른 사람들은 그렇게 하지도 않았습니다.
- 누적 매치 패턴이 뭔지는 모르겠지만 이번에 다른 DP 문제도 비슷할 것 같아서 이렇게 했습니다.
- 2차원 목록 스티커를 만듭니다.
- 처음에는 중첩된 for 문을 써야 하나 고민했는데 곰곰이 생각해보니 스티커가 두 줄로 되어 있어서 그럴 필요가 없다는 생각이 들었습니다.
- 스티커의 윗줄과 아랫줄에 첫 번째 스티커만 놓는다고 가정하면 그 줄의 최대값은 자신이므로 다음과 같이 최대값을 저장하는 dp에 넣습니다.
- dp(1)(1) = 스티커(0)(0)
- dp(2)(1) = 스티커(1)(0)
- 다음 스티커(크기 2×2 이상)를 추가할 때 현재 단계에서 가장 클 수 있는 값을 dp 단위로 입력해야 합니다. 상단 행과 하단 행의 현재 위치에 있을 수 있는 가장 큰 값은 다음 중 하나입니다.
- 지금 입력한 숫자로 계산했을 때 >>> 지금 입력한 숫자와 대각선 역방향 누적합의 합
- 지금 입력한 숫자를 포함하지 않고 계산하는 경우 >>> 지금 입력한 숫자는 무시하고 같은 줄에 나 바로 뒤에 오는 값만 삽입
- 두 경우를 비교하여 현재 위치에 더 큰 값을 넣습니다.
- 위의 계산을 끝까지 반복한 후 각 행의 마지막 열에 있는 값을 비교하여 출력한다.
아래는 전체 코드입니다.
import sys
T = int(sys.stdin.readline())
for testcase in range(T):
N = int(sys.stdin.readline())
sticker = ()
dp = ((0) * (N + 1) for _ in range(3))
for _ in range(2):
sticker.append((*map(int, sys.stdin.readline().split())))
for i in range(1, N + 1):
if i == 1:
dp(1)(i), dp(2)(i) = sticker(0)(0), sticker(1)(0)
else:
dp(1)(i) = max(dp(2)(i - 1) + sticker(0)(i - 1), dp(1)(i - 1))
dp(2)(i) = max(dp(1)(i - 1) + sticker(1)(i - 1), dp(2)(i - 1))
# print(dp(-1)(-1)) >>> 첫 시도 때 이렇게 해서 '틀렸습니다' 가 나왔다.
print(max(dp(1)(-1), dp(2)(-1)))
DP 문제가 왜 이렇게 어려운지 모르겠습니다…