Enochkon's blog

문제

코드

T = int(input())
for _ in range(T):
    N = int(input())
    arr = [list(map(int,input().split()))]
    arr.append(list(map(int,input().split())))
    res=[[0 for _ in range(N+1)] for _ in range(2)]
    for i in range(N):
        if(i==0):
            res[0][i+1]=arr[0][i]
            res[1][i+1]=arr[1][i]
            continue
        res[0][i+1]=max(res[1][i]+arr[0][i],res[1][i-1]+arr[0][i])
        res[1][i+1]=max(res[0][i]+arr[1][i],res[0][i-1]+arr[1][i])
    print(max(max(res[0]),max(res[1])))

풀이

1. 시행횟수 T와 스티커사진의 길이 N, 그리고 각 스티커의 점수를 입력 받는다.
2. 입력 받은 스티커 사진을 조건에 맞게 찢어서 최대 점수를 얻는 방법을 구한다. (res배열은 해당 위치 최고 점수의 합)1 2

   1	2
   		3

   1. 우선 첫번째 위치의 경우에는 온전히 res배열에 그 스티커의 점수를 저장한다.
   2. 두번째부터 점화식을 세워서 구해준다.
   3. 위의 표처럼 이런 상황에서 3의 최대값을 구하려면 우선 (2까지의 점수합 + 3의 점수)이 있다. 그리고 또한 스티커를 뗀 부분의 상하좌우를 못쓰게 되므로 만약 1까지의 점수합이 더 크다면 (1까지의 점수합 + 3의 점수) 의 경우가 존재한다. 즉 max((2까지의 점수합 + 3의 점수), (1까지의 점수합 + 3의 점수))을 구하게 된다면 해당 위치의 스티커의 최대점수를 얻을 수 있다.
   4. 끝까지 최대점수를 구한뒤 max()함수를 사용하여 최대값을 구한 후 출력해준다.