코딩코양이코리

문제 코드import sysinput = sys.stdin.readlinen = int(input())lst = [int(input()) for _ in range(n)]dp = [0]*nif len(lst) 2:    print(sum(lst))else:    dp[0] = lst[0]    dp[1] = lst[0] + lst[1]    for i in range(2, n):        # dp[i-3]+lst[i-1]과 dp[i-2]의 최댓값        # 즉 0, 2 -> 3으로 간 것과 0, 1 -> 3 간 것의 최댓값을 구함        dp[i] = max(dp[i-3]+lst[i-1]+lst[i], dp[i-2]+lst[i])    # 마지막 계단까지 최대 점수 출력    print(..

풀이방법 DP문제이다. 2차원 배열을 4등분하기좌표 r, c가 2배가 됨에 따라 값이 4의 배수로 확장하는 규칙을 찾을 수 있음. (r % 2, c % 2)로 현재 위치 (r, c)가 속한 2x2 배열에서의 상대적인 위치를 나타냄2*(r % 2) + (c % 2)로 상대적인 위치를 기반으로 한 사분면의 인덱스를 계산재귀적으로 이전 단계로 이동:배열을 2^N x 2^N에서 2^(N-1) x 2^(N-1)로 줄임int(r / 2), int(c / 2)는 현재 위치를 절반으로 나누어 새로운 위치를 계산 현재 위치에 대한 순서 합산:4 * sol(N-1, int(r/2), int(c/2))는 이전 단계에서 얻은 순서를 현재 사분면 크기(4배)만큼 확장2*(r % 2) + (c % 2)는 현재 단계에서의 상대적인..