Jinho Tech

기본적인 다이나믹 프로그래밍 문제이다. 뒤쪽 대각선 방향으로 첫 번째, 두 번째 위치의 값 중 큰 걸 선택하면 된다.

dp[0][j] += max(dp[1][j-1], dp[1][j-2]) 

dp[1][j] += max(dp[0][j-1], dp[0][j-2])

for _ in range(int(input())):
    n = int(input())
    dp = [[0]+list(map(int, input().split())) for _ in range(2)]    
    for j in range(2, n+1):
        dp[0][j] += max(dp[1][j-1], dp[1][j-2])
        dp[1][j] += max(dp[0][j-1], dp[0][j-2])
    print(max(dp[0][n], dp[1][n]))

이런 DP 비슷한 문제들은 아직 어색해서 푸는데 오래 걸렸다.

변을 공유하는 현재 스티커를 고른다면 위 혹은 밑, 양옆의 스티커는 포기해야 하는데,

이전 대각선과 전전 대각선의 값을 현재 값과 각각 더해 비교하여 큰 값을 취하는 방식으로 문제를 풀었다.

for _ in range(int(input())):
    n = int(input())
    
    li = []
    for _ in range(2):
        li.append(list(map(int, input().split())))
    
    li[0][1] += li[1][0]
    li[1][1] += li[0][0]
    
    for j in range(2, n):
        li[0][j] += max(li[1][j - 1], li[1][j - 2])
        li[1][j] += max(li[0][j - 1], li[0][j - 2])
    
    ans = max(li[0][n - 1], li[1][n - 1])
    print(ans)