[백준 9465번] 스티커 (Python 파이썬) 풀이 방법

백준 9465번 <스티커> 문제 보기

https://www.acmicpc.net/problem/9465

9465번: 스티커

 

 

백준 9465번 <스티커> 문제 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

T = int(input())
result = []

for _ in range(T):
  n = int(input())
  array = [list(map(int, input().split())) for _ in range(2)]

  if n == 1:
    print(max(array[0][0], array[1][0]))
    continue
  
  dp = [[0]*n for _ in range(2)]
  dp[0][0] = array[0][0]
  dp[1][0] = array[1][0]
  dp[0][1] = array[1][0] + array[0][1]
  dp[1][1] = array[0][0] + array[1][1]
  
  for i in range(2, n):
    dp[0][i] = max(dp[1][i-2], dp[1][i-1]) + array[0][i]
    dp[1][i] = max(dp[0][i-2], dp[0][i-1]) + array[1][i]

  result.append(max(dp[0][-1], dp[1][-1]))

print(*result, sep = "\n")

 

 

그림이 살짝 잘못 되어 있지만, z로 올 수 있는 발판은 a 혹은 b이다.

 

• DP 문제
• (z의 최댓값) = max(a의 최댓값, b의 최댓값) + (z의 점수)
• n=1 혹은 n=2 인 경우 for 반복문을 돌지 않고 따로 값 설정
• dp 리스트의 마지막 라인 두 값 중 큰 값을 출력

 

 

 

다른 풀이

import sys
input = sys.stdin.readline

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

  if n ==1:
    print(max(card[0][0], card[1][0]))
    continue

  dp[0][0],dp[1][0] = card[0][0],card[1][0]
  dp[0][1] = card[0][1] + dp[1][0]
  dp[1][1] = card[1][1] + dp[0][0]

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

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

 

• 거의 동일한 풀이 방법

 

t = int(input())
for _ in range(t):
    n = int(input())

    arr = []

    for _ in range(2):
        arr.append(list(map(int,input().split())))

    if n == 1:
        print(max(arr[0][0],arr[1][0]))
        continue

    for j in range(1,n):
        if j==1:
            arr[0][1] += arr[1][0]
            arr[1][1] += arr[0][0]

        else:
            arr[0][j] += max(arr[1][j-1] , arr[1][j-2])
            arr[1][j] += max(arr[0][j-1] , arr[0][j-2])
    print(max(arr[0][n-1],arr[1][n-1]))

• dp 리스트를 따로 두지 않고 입력받은 arr에 바로 값을 수정해서 저장
• j==1일 경우를 따로 반복문 안에 두었음