[SW expert] #12543. 부분집합의 합2

알고리즘 유형별 문제 모아 풀기 첫번째는 BFS와 Stack.
그간 프로젝트 때문에 자바스크립트와 더 친해져서 알고리즘도, 파이썬도 거의 잊어먹을 지경에 이르러버렸다...!
그래서 다시 꾸준히 알고리즘 공부를 하자! 하고 다짐중.

---

부분집합의 합, 이 문제는 전에도 DFS로 풀었던 문제였고 경우의 수를 따지기만 해도 풀리는 문제다.
최종적으로 Pass한 정답. 전에 제출한 버전보다 실행시간도, 메모리도 높다.

• 92,292 kb메모리
• 5,647 ms실행시간

# DFS로 풀기
# {1,2,3} {2,1,3} 중복문제 => for 문 대신 num에 +1 구조로 만들고 num이 선택 됐는지 아닌지 2가지 경로로 가면 됨.
# path는 디버깅용
# 오류(50/37개만 맞음) => 
# 10번째 라인이 틀렸었음. 'num>20'이 아니라 num>21이어야 마지막 숫자가 포함된 상태의 부분집합 구할 수 있다.

def DFS(num, count, sum, path):
    global N
    global K
    global result

    if num > 21:
        return

    if count == N:
        if sum == K:
            result += 1
        return
            
    if sum >= K:
        return

    DFS(num+1, count+1, sum+num, path+str(num)) #num이 부분집합 포함
    DFS(num+1, count, sum, path) #num이 부분집합 불포함

T = int(input())

for test in range(1, T+1):
    N, K = map(int, input().split())
    result = 0
    DFS(1, 0, 0, '')
    print('#{} {}'.format(test, result))

맨 처음에 작성한 코드는 진짜 엉망이었음.
너무 오랜만이라 진짜 아무것도 기억 안나서  '어.. 중복이 발생하면 안되니까 set에 넣다 뺐다 해줄까..?'하다
실행시간 초과 나옴.

예전에 했던 제출한 답안 코드를 다시 꺼내봤는데 메모리도, 실행시간도 훨씬 효율적이다.

• 69,080 kb메모리
• 30,006 ms실행시간

def dfs(num, sum,cnt, path):
    global N
    global K
    global ret
    if num == 21:
        if sum == K and cnt == N:
            ret += 1
        return
 
    dfs(num+1, sum+num, cnt + 1,path+str(num)) # 부분집합에 포함
    dfs(num+1, sum,cnt,path) # 부분집합에 안포함
    return
 
 
T = int(input())
for test_ in range(1, T+1):
    N, K = map(int, input().split())
    ret = 0
    dfs(1,0,0,"")
    print('#{} {}'.format(test_, ret))

왜인가 했더니 전에 작성한 버전은 케이스를 모두 거슬러 갔을 때 sum이 K와 같고 cnt가 N과 같은 것을 찾는 식으로 짜서 결과 값을 도출하는 식이고, 최근 작성 버전은 num이 20까지 향하는 도중에 count 개수가 같을 때를 찾아서 그런 듯.