📚 9465 - 스티커

스티커

내가 푼 소스

t = int(input())

for _ in range(t):
    n = int(input())
    list_array = []
    dp = [[0] * (n) for _ in range(2)]

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

    dp[0][0] = list_array[0][0]
    dp[1][0] = list_array[1][0]

    for j in range(1, n):
        for i in range(2):
            if i == 1:
                cur_i = 0
            else:
                cur_i = 1

            if j == 1:
                # print("i, j", i, j, "결과 : ", dp[cur_i][j - 1])
                dp[i][j] = dp[cur_i][j - 1] + list_array[i][j]
            else:
                # print("i, j", i, j, "결과 : ", dp[cur_i][j - 2], dp[cur_i][j - 1])
                cur_data = max(dp[cur_i][j - 2], dp[cur_i][j - 1]) + list_array[i][j]
                if cur_data > dp[i][j]:
                    dp[i][j] = cur_data

    zero = max(dp[0])
    one = max(dp[1])

    print(max(zero, one))

상위권 효율적인 코드
참고 : https://pacific-ocean.tistory.com/197

• 일단 양 옆의 숫자는 선택할 수 없다는 것을 인지하고 있어야 한다.
• 1번 인덱스에는 왼쪽 대각선의 숫자를 더할 수 있다.
• 2번째 인덱스부터는 이때까지 최댓값을 더한 숫자를 저장하고 있는 왼쪽 대각선의 숫자, 또는 그 왼쪽 숫자를 더할 수 있다. 이 둘중에 큰 값을 더해주면 된다.

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

실행 결과

간단한 코드상에서는 Python3가 메모리, 속도 측에서 우세하다.
복잡한 코드을 사용하는 경우 PyPy3가 우세하다.