[Python] 9495. 스티커

tc = int(input())

for _ in range(tc):
    n = int(input())    # 한 라인의 스티커 개수
    dp = [list(map(int, input().split())) for _ in range(2)]   # 주어진 스티커 배열

    if n > 1:
        dp[0][1] += dp[1][0]    # 점화식에 i-2가 있기때문에 처음 값은 직접 더해준다. (현재자리의 왼쪽 대각선자리)
        dp[1][1] += dp[0][0]
        for i in range(2, n):
            # 선택할 수 있는 두 자리에 있는 점수 중, 큰 점수와 현재 스티커와 더해주기
            dp[0][i] += max(dp[1][i-2], dp[1][i-1]) 
            dp[1][i] += max(dp[0][i-2], dp[0][i-1])

    print(max(dp[0][-1], dp[1][-1]))    # 마지막 자리에서 여태까지 더한 제일 큰 점수 선택

점화식 설명 

• i = 9라고 한다면, 9 자리에서는 7과 10의 자리를 택할 수 없다. 그렇기에 9의 자리에서 택할 수 있는 자리는 6과 8이 남는다. (5의 경우는 5를 택하면 8도 택할 수 있기 때문) 그렇기 때문에 점화식은 max(dp[0 or 1][i-2], dp[0 or 1][i-1])이 된다.
  그렇기 때문에 둘 중 더 큰 점수를 저장하고 있는 곳을 택하고, 해당 자리의 점수를 더하면 해당 자리에서 고를 수 있는 최대 점수가 된다. 
• 그리고 1의 자리 (dp[0][0])에서 출발한 경우와 2의 자리(dp[1][0])에서 출발한 경우. 이렇게 두가지 수가 나오니 마지막에 둘 중에 더 큰 점수를 정답으로 가진다.
  

 

 

처음 풀이

tc = int(input())

for _ in range(tc):
    n = int(input())    # 한 라인의 스티커 개수
    sticker = [list(map(int, input().split())) for _ in range(2)]   # 주어진 스티커 배열

    dp = [[0 for _ in range(n)] for _ in range(2)]  # dp 배열
    dp[0][0] = sticker[0][0] # 초기 스티커 넣어주기
    dp[1][0] = sticker[1][0]
    if n == 1:
        print(max(dp[0][0], dp[1][0]))
    else:
        dp[0][1] = sticker[1][0] + sticker[0][1]
        dp[1][1] = sticker[0][0] + sticker[1][1]
        for i in range(2, n):
            # 선택할 수 있는 두 자리에 있는 점수 중, 큰 점수와 현재 스티커와 더해주기
            dp[0][i] = max(dp[1][i-2], dp[1][i-1]) + sticker[0][i] 
            dp[1][i] = max(dp[0][i-2], dp[0][i-1]) + sticker[1][i]

        print(max(dp[0][-1], dp[1][-1]))    # 마지막 자리에서 여태까지 더한 제일 큰 점수 선택

dp 배열을 만들어서 거기에 해당자리에서 구할 수 있는 최대 점수를 넣어주는 코드로 짰는데, 풀고 보니 dp 배열을 굳이 새로 만들어 줄 필요가 없다고 생각하여 맨 위의 코드처럼 수정하게 되었다.