★복습필요[python_파이썬_Half Pass]백준_1182번_부분수열의합_백트래킹_풀이

공부하는허딩크 : https://www.youtube.com/live/H0kM09bxI4I?feature=shared

※부분수열의 정의 => 부분수열이라는 조건을 받으면 아래의 조건을 생각해야함.
주어진 수열에서 순서를 유지하면서 일부 원소를 선택하여 만든 새로운 수열을 의미한다.
1. 순서 유지 : [1, 2, 3]이라면 [2, 1]은 부분수열이 될 수 없다.
2. 중복 선택 불가
 
<첫번째 시도 : 맞았습니다.>
일단 itertools.combinations로 해결했다.
중간에 오류가 있었는데 nums 변수를 받을 때 list()로 만들지 않아서 계속 오류가 났다.
list변수를 만들어 줘야 제대호 작동한다.

import sys

import itertools

input = sys.stdin.readline

N, S = map(int, input().split())

nums = list(map(int, input().split()))

cnt = 0

for i in range(1, N + 1):

    num = list(j for j in itertools.combinations(nums, i))

    for k in num:

        if sum(k) == S:

            cnt += 1

print(cnt)

 
<두번째 시도 : 시간초과>
일단  파이썬에서는 돌아가는데 백준에서는 시간초과가 뜬다.
근데 이 코드는 일단 이상하다. 
자.  뭐가 이상할까?? 고민중 고민중.......아니 그냥 뭐가 잘못 된거 같다. 방향을 다르게 하자. index중심으로.

import sys

input = sys.stdin.readline

N, S = map(int, input().split())

nums = list(map(int, input().split()))

cnt = 0

def combi(seq):

    global cnt

    print(seq)

    if sum(seq) == S:

        cnt += 1

        return

   

    for i in nums:

        if i not in seq:

            combi(seq + [i])

       

combi([])

print(cnt)

 
일단 포기하고 다른 사람 풀이 참고. (위에 코드를 활용하고 싶은데 답이 안나온다. ㅜ)
<세번째 시도 : 맞았습니다.>
이게 되네?? 이게 맞지. 계속 if문에서 return을 줘야 한다는 고정관념을 내려 놓았다.
그리고 seq가 빈 리스트일때도 sum(seq)의 값도 0이 나온다는 것을 놓쳤다.
def combi함수로 들어갈때 마다 print를 해서 체크를 해주면 아래와 같이 나온다.
[] 0
[-7] -7
[-7, -3] -10
[-7, -3, -2] -12
[-7, -3, -2, 5] -7
[-7, -3, -2, 5, 8] 1
[-7, -3, -2, 8] -4                 => 이 부분부터 이해가 잘 안되네? 왜 이렇게 나올까? (아래 print추가 후 점검)
[-7, -3, 5] -5
[-7, -3, 5, 8] 3
[-7, -3, 8] -2
[-7, -2] -9
[-7, -2, 5] -4
[-7, -2, 5, 8] 4
[-7, -2, 8] -1
[-7, 5] -2
[-7, 5, 8] 6
[-7, 8] 1
[-3] -3
[-3, -2] -5
[-3, -2, 5] 0
[-3, -2, 5, 8] 8
[-3, -2, 8] 3
[-3, 5] 2
[-3, 5, 8] 10
[-3, 8] 5
[-2] -2
[-2, 5] 3
[-2, 5, 8] 11
[-2, 8] 6
[5] 5
[5, 8] 13
[8] 8
1
★엑셀로 아래와 같이 정리했다. 재귀함수가 종료되어 다시 시작되는 부분을 모두 구분했다.
   아직 재귀함수에 대한 이해도가 많이 부족한 것 같다. 조금 더 공부해보자.!!! 머리에 때려 넣어보자!!!!

import sys

input = sys.stdin.readline

N, S = map(int, input().split())

nums = list(map(int, input().split()))

cnt = 0

"""index기준 depth추가"""

def combi(seq, start):

    global cnt

    #print(seq, sum(seq))

    if sum(seq) == S and seq:

        cnt += 1

   

    for i in range(start, N):

        """i + 1로 index중심 부분수열 만들기"""

        combi(seq + [nums[i]], i + 1)

       

combi([], 0)

print(cnt)

 
<다른 사람 풀이 참고 : 이 코드가 이해가 안되는데 복습해보자!>

import sys

input = sys.stdin.readline

n, s = map(int, input().split())

arr = list(map(int, input().split()))

cnt = 0

def subset_sum(idx, sub_sum):

    global cnt

    if idx >= n:

        return

    sub_sum += arr[idx]

    if sub_sum == s:

        cnt += 1

   

    # 현재 arr[idx]를 선택한 경우의 가지

    subset_sum(idx+1, sub_sum)

    # 현재 arr[idx]를 선택하지 않은 경우의 가지

    subset_sum(idx+1, sub_sum - arr[idx])

subset_sum(0, 0)

print(cnt)

 
 
 
<회사 점심 시간에 메모>
백트레킹 문제
1. itertools로 문제 풀이시 문제의 조건은 N개의 정수로 이루어진 수열이 있을때, 크기가 양수인 부분수열 중에서..를 읽고 어떤 라이브러리를 사용해야 할지 판단 필요.
permutaions는 중복 없고, (1, 2)와 (2, 1)을 다르게 판단함으로 필요 없음
combinations는 중복 없고, (1, 2)와 (2, 1)을 동일하게 판단함
다른 것들은 중복이 있으니까 안됨.
이 문제를 읽고 이게 판단이 되는건가??? 2번째 풀어보는데 판단이 안되는데 ;;;;