백준 9465번 스티커 파이썬 풀이

백준 9465 스티커

풀이

우선, 대각선으로만 뜯을 수 있다는 사실을 알 수 있다. 그런데, 연속해서 대각선으로 안뜯고 넘길 수도 있다. 

그래서 두번 째 전의 것도 비교해서 더 큰 것을 더해가면 된다.

 

1. 처음 입력받는 것은 테스트 케이스 개수이다. 개수만 큼 for문을 돌려줄 것이다.

a = int(input())

 

2. b에는 2n개 스티커의 n이 들어간다. c=[0,0]를 미리 만들어서 리스트 맵으로 입력값을 받는다.

for i in range(a):

  b = int(input())

  c = [0,0]

  c[0] = list(map(int,input().split()))

  c[1] = list(map(int,input().split()))

 

3. 1부터 b-1만큼 돌 것이다. 인덱스는 0부터 시작하고, 우리는 이전의 값을 더해줄 것이기 때문에 1부터 시작한다.

1일 때는 대각선 값들을 더해준다.

1이 아니라면(2 이상) 대각선 값과 그 뒤의 값 중에 큰 것을 더한다.

  for i in range(1,b):

    if i==1:

      c[0][i]+=c[1][i-1]

      c[1][i]+=c[0][i-1]

    else:

      c[0][i]+=max(c[1][i-1],c[1][i-2])

      c[1][i]+=max(c[0][i-1],c[0][i-2])

 

4. 마지막까지 더한 값 중에서 더 큰 값을 출력한다.

  print(max(c[0][b-1],c[1][b-1]))