BAEKJOON : 9465

No. 9465

1. Problem

2. My Solution

• n 이 증가할 때 1행의 스티커를 고르는 경우, 2행의 스티커를 고르는 경우, 고르지 않는 경우로 나뉨
• i = n 이고 j 는 0,1,2 로 어떤 스티커를 고르는지에 대한 정보를 저장하는 dp[i][j] 이용
• i 번째 스티커까지 존재할 경우 i-1 번째의 최대값을 이용

# dp[i][j] -> i = n, j = 0,1,2 (0 = 선택 x, 1 = 1행, 2 = 2행)

import sys

test_n = int(sys.stdin.readline().rstrip())

for _ in range(test_n):
    n = int(sys.stdin.readline().rstrip())

    sticker = []
    sticker.append([0]+ (list(map(int,sys.stdin.readline().rstrip().split()))))
    sticker.append([0]+ (list(map(int,sys.stdin.readline().rstrip().split()))))

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

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

    print(max(dp[n]))

3. Others' Solutions

• i 번째 점수를 계산할 때 i-1 번째 스티커를 고르지 않는 경우를 판단하기 위해 i-2 이용
• 1행의 스티커를 고를 때 i-2 에서 2행의 경우만 판단하는 이유는 i-1 에서 이미 판단되기 때문

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    dp = []
    dp.append(list(map(int, input().split())))
    dp.append(list(map(int, input().split())))

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

    print(max(dp[0][n-1], dp[1][n-1]))

4. Learned

• 다른 사람들의 코드를 분석해보는 연습도 중요함