문제 개요
숫자로 이루어진 리스트 nums와 양수 K가 주어집니다. 우리는 각 원소에 대해 다음 세 가지 연산 중 하나를 한 번씩만 적용할 수 있습니다.
- 하나의 숫자를 음수로 만들기
- 숫자 자신에게 인덱스(1부터 시작)를 더하기
- 숫자 자신에게서 인덱스를 빼기
최종 목표는 각 원소에 위 연산을 최대 한 번씩만 수행하여 배열 전체의 합이 정확히 k가 될 수 있는지 판별하는 것입니다.
예를 들어 입력이 nums = [1,2,3,7], k = 8이라고 가정해 보겠습니다. 이 경우 출력은 True입니다. 값 2와 3에서 각각 자신의 인덱스인 2와 3을 빼면 배열이 [1, 0, 0, 7]이 되고, 이때 합은 8로 k와 일치하기 때문입니다.
풀이 접근 방법
이 문제는 메모이제이션(memoization)을 활용한 재귀 탐색으로 효율적으로 해결할 수 있습니다. 각 인덱스에서 가능한 모든 선택지(음수로 만들기, 아무 연산도 하지 않기, 인덱스 빼기, 인덱스 더하기)를 재귀적으로 시도하며 목표 합계에 도달할 수 있는지 확인하고, 동일한 상태의 중복 계산을 테이블에 저장하여 피합니다.
알고리즘 단계
size를 100으로 설정합니다.is_ok()함수를 정의합니다. 이 함수는 매개변수로 i, total, k, nums, table을 받습니다.- n := nums의 크기
- total <= 0이면 False를 반환합니다.
- i >= n이면, total == k일 때 True를, 그렇지 않으면 False를 반환합니다.
- table[i][total]이 -1이 아니라면 이미 계산된 상태이므로 해당 값을 그대로 반환합니다.
- 다음 네 가지 경우를 재귀적으로 탐색합니다.
- 현재 원소를 음수로 만드는 경우: total에서 2 * nums[i]를 뺍니다.
- 연산을 적용하지 않는 경우: total을 그대로 유지합니다.
- 인덱스를 빼는 경우: total에서 (i+1)을 뺍니다.
- 인덱스를 더하는 경우: total에 (i+1)을 더합니다.
- 메인 함수에서는 total을 nums의 전체 합으로 초기화하고, -1로 채운 2차원 테이블을 생성한 뒤
is_ok(0, total, k, nums, table)을 호출합니다.
아래 구현 예시를 통해 더 잘 이해해 보겠습니다.
예제 코드
size = 100
def is_ok(i, total, k, nums, table):
n = len(nums)
if total <= 0:
return False
if i >= n:
if total == k:
return True
return False
if table[i][total] != -1:
return table[i][total]
table[i][total] = is_ok(i + 1, total - 2 * nums[i], k, nums, table) or is_ok(i + 1, total, k, nums, table)
table[i][total] = is_ok(i + 1, total - (i + 1), k, nums, table) or table[i][total]
table[i][total] = is_ok(i + 1, total + i + 1, k, nums, table) or table[i][total]
return table[i][total]
def solve(nums, k):
total = sum(nums)
table = [-1] * size
for i in range(size):
table[i] = [-1] * size
return is_ok(0, total, k, nums, table)
nums = [1, 2, 3, 7]
k = 8
print(solve(nums, k))
입력
[1,2,3,7], 8
출력
True
정리
이 알고리즘은 각 원소마다 네 가지 선택지를 깊이 우선 탐색 방식으로 확인하므로, 메모이제이션 덕분에 동일한 (인덱스, 합계) 상태를 반복 계산하지 않습니다. 따라서 배열의 크기와 합계 범위가 제한적인 경우에도 실용적인 시간 안에 답을 구할 수 있습니다.