문제 개요
숫자 리스트 nums와 두 변수 k, t가 주어져 있다고 가정해 보겠습니다. 이 문제에서 수행할 수 있는 연산은 범위 [-k, k] 안에서 임의의 값 e를 하나 선택해 리스트 nums의 끝에 삽입하는 것입니다. 이러한 연산을 반복했을 때 nums의 총합이 목표값 t와 정확히 일치하도록 만드는 데 필요한 최소 연산 횟수를 구하는 것이 목표입니다.
예를 들어 입력이 nums = [3, 1], k = 4, t = 19라면 답은 4가 됩니다. [3, 1, 4, 4, 4, 3]처럼 값을 네 번 추가하면 합이 정확히 19가 되기 때문입니다.
접근 방법
핵심 아이디어는 매우 단순합니다. 한 번의 연산으로 합계를 최대 k만큼 늘리거나 줄일 수 있으므로, 현재 합계와 목표값 사이의 차이를 k로 나눈 뒤 올림하면 그 값이 곧 최소 연산 횟수가 됩니다.
total := nums에 포함된 모든 요소의 합
diff := |t − total| (목표값과 현재 합의 차이)
result := diff ÷ k의 몫(내림)
만약 result × k가 diff와 같지 않다면, 즉 나누어떨어지지 않는다면 result에 1을 더해 올림 처리
result 반환
예제 코드
다음 구현을 통해 동작 방식을 더 자세히 살펴보겠습니다.
def solve(nums, k, t): total = sum(nums) diff = abs(t - total) result = diff // k if result * k != diff: result = result + 1 return result nums = [3, 1] k = 4 t = 19 print(solve(nums, k, t))
입력
[3, 1], 4, 19
출력
4
시간 및 공간 복잡도
리스트의 합을 한 번만 계산하므로 시간 복잡도는 O(n)이며, 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 이처럼 올림 나눗셈 하나로 문제를 해결할 수 있어 매우 효율적인 풀이입니다.