[dp/백준] 9465번: 스티커

-문제:https://www.acmicpc.net/problem/9465

 

처음에 bfs로 풀어야하나 싶었는데 이걸로 풀면 안되는게 

상,하,좌,우의 값을 확인하는 것이 아니라 이것들을 빼고 진행하는 거라서 탐색으로 진행하면 안된다 

 

인덱스에 따라서 더할 수 있는 값들 중 최댓값을 더해가다가 마지막 열의 두 값 중 더 큰 값을 출력하면 된다 

아직 스스로 푼건 아니지만, 다이나믹 프로그래밍 문제를 풀면서 느낀게 값을 누적하고, 최댓값을 적용해야하는 상황을 잘 판단해야지 문제를 잘 풀 수 있겠다 라는 생각을 한다

 

-정답풀이 

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