파이썬으로 목표 배열 만들기: 부분 배열 증가 연산의 최소 횟수 구하는 방법

문제 설명

양의 정수로 이루어진 target(목표) 배열이 하나 주어집니다. 또한 크기가 같고 모든 원소가 0으로 채워진 initial(초기) 배열이 있다고 가정합니다. 우리는 아래와 같은 연산만을 반복해서 초기 배열을 목표 배열로 바꿔야 하며, 이때 필요한 최소 연산 횟수를 구해야 합니다.

• 연산 정의: 배열에서 임의의 부분 배열(연속된 구간)을 하나 선택하고, 그 구간에 속한 모든 값을 1씩 증가시킵니다.

입출력 예시

예를 들어 입력이 target = [2,3,4,3,2]라고 해보겠습니다. 이 경우 정답은 4입니다. 과정은 다음과 같습니다.

1. 초기 배열은 [0,0,0,0,0]입니다.
2. 인덱스 0~4 구간을 선택해 1씩 더하면 [1,1,1,1,1]이 됩니다.
3. 다시 인덱스 0~4 구간을 선택하면 [2,2,2,2,2]가 됩니다.
4. 인덱스 1~3 구간을 선택해 증가시키면 [2,3,3,3,2]가 됩니다.
5. 마지막으로 인덱스 2만 선택해 증가시키면 [2,3,4,3,2]로 목표 배열과 동일해집니다.

풀이 접근 방법

핵심 아이디어는 간단합니다. 배열을 왼쪽에서 오른쪽으로 한 번 훑으면서, 현재 값이 이전 값보다 커질 때마다 그 증가분만큼 새로운 연산이 시작된다고 보는 것입니다. 값이 감소하거나 같아지는 구간은 이미 진행 중인 연산에 포함되므로 추가 연산이 필요하지 않습니다.

구체적인 알고리즘은 다음과 같습니다.

• prev_num := 0 — 이전 원소의 값을 저장합니다(처음에는 0).
• steps := 0 — 총 연산 횟수를 저장합니다.
• target의 각 원소 val에 대해 반복합니다.
  • val > prev_num이면 steps += val - prev_num을 수행하고, 그렇지 않으면 아무것도 더하지 않습니다.
  • prev_num := val로 값을 갱신합니다.
• 반복이 끝나면 steps를 반환합니다.

파이썬 구현 예제

아래 코드로 직접 실행하며 확인할 수 있습니다.

def solve(target):
    prev_num = 0
    steps = 0
    for val in target:
        steps += val - prev_num if val > prev_num else 0
        prev_num = val
    return steps

target = [2, 3, 4, 3, 2]
print(solve(target))

입력

[2, 3, 4, 3, 2]

출력

4

동작 원리 정리

예시 배열 [2,3,4,3,2]에 이 알고리즘을 적용해 보면 다음과 같습니다.

• 첫 번째 원소 2: 0에서 2로 증가 → 2회 추가 (누적 2)
• 두 번째 원소 3: 2에서 3으로 증가 → 1회 추가 (누적 3)
• 세 번째 원소 4: 3에서 4로 증가 → 1회 추가 (누적 4)
• 네 번째 원소 3: 감소 → 추가 없음
• 다섯 번째 원소 2: 감소 → 추가 없음

따라서 총 연산 횟수는 4가 되며, 실제 시뮬레이션 결과와 일치합니다. 이 방법은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적이라는 장점이 있습니다.