[백준/Python] 1182번 : 부분 수열의 합

오늘 시험에 나온 문제인데 45분을 투자했음에도 제 시간 안에 못 풀었다.

재귀 탐색 아이디어는 맞았는데 종료 조건이 틀렸고 재귀 인자로 넘기는 값이 뭔지 정확하게 파악하지 못했고

문제 조건을 제대로 고려하지 않았다. 

문제 분석

https://www.acmicpc.net/problem/1182

5 0 //N원소개수 S부분수열의 합
-7 -3 -2 5 8 //수열

 

주어진 수열에서 부분 수열의 원소 개수 합이 S가 되는 경우가 몇 개인지 구하는 문제이다.

위와 같이 주어진 경우 [-3, -2, 5] 한 가지 있으므로 답은 1

 

아이디어?

부분 수열을 만들려면 N개의 원소 각각이 선택되거나 선택되지 않아야 한다.

-> 두 가지 경우를 나누어 재귀 호출

 

오답노트

틀린 코드 :

numbers = [input받은 list]
cnt = 0
def recur(sum: 지금까지 선택한 숫자들의 합, start: 지금 선택할 숫자의 인덱스):
	global cnt
    if sum == S:
    	cnt += 1
        return
    for i in range(start, N+1):
    	recur(sum+numbers[i], i+1)

# 호출부
recur(0, 0)
print(cnt)

import sys

N, S = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))

cnt = 0
def recur(sum_, index):
    global N, S, cnt

    if index>N-1: # 범위 밖을 참조하는 경우
        return

    if sum_ == S: # 합이 S인 부분 수열을 찾음
        cnt += 1
        return

    recur(sum_ + numbers[index], index + 1) # 다음 인접한 숫자 선택하러 가기

for i in range(0, N):
    recur(numbers[i], i+1)
print(cnt)

맨 처음 짰던 코드다. (위쪽은 수도코드)

0번째 요소부터 N번째 요소까지 시작점으로 잡고 인접한 요소들을 하나씩 더해가면서 합이 S인지 확인한다.

탐색 중 합이 S인 경우를 찾으면 cnt를 올려준다. 

인덱스 에러가 떠서 범위 밖을 참조하는 경우 재귀를 종료하는 조건을 추가했다.

 

✔️ 틀린 이유?

• 부분 수열을 인접한 요소들로만 생성함
• 부분 수열 [ ] 을 카운트에서 제외하지 않았음

문제에는 명시되지 않았지만 슬랙에 있었는데 내가 제대로 읽어보지 않고 풀었다.

결국 시험이 종료 되고 이 조건들을 놓친 것을 알게 되었다.

내가 간과한 조건들

• 길이가 1인 부분 수열은 고려하지 않음
  -> i번째 요소를 무조건 선택하고 다음 요소를 찾으러 재귀로 넘어가고 있음
• 재귀 종료 조건을 합이 S인 경우로 설정함
  -> 합이 S인 경우에도 계속해서 탐색해야 함
  예) S가 2이면 [4, -2]를 찾았더라도 [4, -2, -1, 1]과 같은 경우가 있을 수 있기 때문

수정한 코드:

import sys

N, S = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))

cnt = 0
def recur(sum_, index):
    global N, S, cnt

    if index==N: # 모든 원소를 다 탐색했을 때
        if sum_ == S: # 합이 S인 부분 수열을 찾음
            cnt += 1
        return

    # 다음 요소 선택하러 가기
    recur(sum_+numbers[index], index + 1) # 현재 원소를 선택하는 경우
    recur(sum_, index+1) # 현재 원소를 선택하지 않는 경우

recur(0, 0)

if S==0: # S가 0일 때 공집합이 포함되므로 카운트에서 제외
    cnt-=1
print(cnt)

 

• 부분 수열을 생성할 때 불연속적으로 요소를 선택할 수 있게 만듦
  -> 다음 요소를 선택하러 재귀를 보낼 때 현재 턴에서 요소를 선택하는 경우, 선택하지 않는 경우 두 가지를 생성
• S가 0인 경우 아무 요소도 선택하지 않은 공집합 [ ]의 경우에도 카운트를 세는데, 공집합은 부분 수열이 아니므로 카운트를 하나 빼준다.
• 특정 원소 하나만 선택하고 나머지 원소를 모두 선택하지 않으면 원소가 하나인 부분 수열을 만들 수 있음
• 재귀 종료 조건을 sum==S가 아닌 index==N으로 설정하여 모든 부분 수열을 놓치지 않고 구할 수 있게 함

다음에 다시 풀어봐야지