파이썬으로 규칙에 따라 생성한 배열에서 최댓값 찾는 프로그램

문제 설명

숫자 n이 주어졌을 때, 다음 규칙에 따라 길이가 n+1인 배열 A를 생성해야 합니다.

• A[0] = 0
• A[1] = 1
• 2 ≤ 2×i ≤ n일 때, A[2×i] = A[i]
• 2 ≤ 2×i+1 ≤ n일 때, A[2×i+1] = A[i] + A[i+1]

배열 생성이 완료되면, 배열 안에서 가장 큰 값을 찾아 반환하면 됩니다.

예시

n = 5가 입력으로 주어지면 결과는 3이 됩니다. 실제로 배열을 하나씩 만들어 보면 다음과 같습니다.

• A[0] = 0
• A[1] = 1
• A[2] = A[1] = 1
• A[3] = A[1] + A[2] = 1 + 1 = 2
• A[4] = A[2] = 1
• A[5] = A[2] + A[3] = 1 + 2 = 3
• A[6] = A[3] = 2

따라서 이 배열의 최댓값은 3입니다.

풀이 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

1. 0부터 n까지의 값으로 초기화된 리스트 A를 생성합니다.
2. A의 각 인덱스 i에 대해 아래 작업을 수행합니다.
   • i가 0 또는 1이면 초깃값을 그대로 두고 다음 반복으로 넘어갑니다.
   • i가 짝수이면 A[i] = A[i // 2]로 설정합니다.
   • i가 홀수이면 A[i] = A[i // 2] + A[(i // 2) + 1]로 설정합니다.
3. 모든 값을 채운 뒤 리스트 A의 최댓값을 반환합니다.

파이썬 구현 예제

아래 코드를 통해 동작 과정을 더 쉽게 이해할 수 있습니다.

def solve(n):
    A = list(range(0, n + 1))
    for i in A:
        if i == 0 or i == 1:
            continue
        elif i % 2 == 0:
            A[i] = A[i // 2]
        else:
            A[i] = A[i // 2] + A[(i // 2) + 1]
    return max(A)

n = 5
print(solve(n))

입력

5

출력

3

복잡도 분석

이 알고리즘은 리스트를 한 번만 순회하면서 각 인덱스의 값을 채워 나가므로 시간 복잡도는 O(n)입니다. 또한 길이가 n+1인 배열 하나만 사용하기 때문에 공간 복잡도 역시 O(n)으로 효율적입니다.