[Python] BOJ(백준) 1182 부분수열의 합

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

 

틀렸던 문제 재도전 두 번째다.

브루트포스, 백트래킹 문제다.

 

처음 문제를 보고 이걸 효율적으로 어떻게 탐색할까... 고민을 했다.

우선 내가 이 문제를 이전에 틀렸었던 이유는 부분수열의 의미를 잘못 파악했기 때문이다.

무조건 연속되는 부분 수열일 것이라고 생각했는데, 임의의 숫자를 선택해서 만들어도 부분수열이었다.

(부분 수열의 확실한 개념은 원래 항에서 무작위로 데이터를 삭제해도 되지만, 그들의 순서는 유지되어야 한다.)

 

처음 생각한 건 투 포인터가 떠올랐는데, 부분 수열을 잘못 알고 있었기에 정렬을 하면 안된다고 생각했다.

(제대로 알고 있었어도 못 쓰는 방법이다.ㅋㅋㅋ)

 

그다음은 누적합을 생각했는데 범위가 괜찮으려나 하고 확인해봤더니 수열의 길이가 최대 20이었다. 

(이 부분도 S의 범위인 1,000,000을 보고 착각했었다...)

범위가 짧은 걸 보고 굳이 누적합을 해야하나? 그냥 이중 포문으로 싹다 탐색해보자. 많아야 400아닌가. 했다.

 

파이썬으로 코드를 짜고, 저번에 틀렸던 코드(C++)를 확인했더니 토씨 하나 안틀리는 똑같은 로직이었다.

그제서야 질문 게시판을 찾아봤더니 연속되지 않아도 부분 수열이라는 점을 확인했다.

# 틀린 코드
import sys

input = sys.stdin.readline
n, s = map(int, input().split())
arr = list(map(int, input().split()))

res = 0
for i in range(n):
    sum = 0
    for j in range(i, n):
        sum += arr[j]
        if sum == s:
            res += 1

print(res)

 

수열의 길이가 짧은 이유는 있다... 백트래킹 문제였다.

백트래킹이 정말 오랜만이라 기억이 잘 안나서 다른 방법을 찾고 싶었는데 떠오르지 않아 선택했다.

 

백트래킹은 정말 모든 경우의 수를 다 따져보는 방법이다.

그래프에서 백트래킹을 사용할 때는 방문 여부로 중복 방문을 막는 것이 중요하지만

해당 문제에서는 한 방향으로 진행하기 때문에 어렵지 않게 구현할 수 있었다.

 

아래 코드는 백트래킹 부분으로, 현재 시점 이후로의 값을 계속 더해보는 것이다.

따라서 dfs의 인자는 현재 인덱스 위치와 현재까지의 합계가 필요하다.

처음에는 if문 내부에 return을 걸었는데 이러면 s라는 값이 나오면 뒤에 값을 더 더해보지 않는다.

def dfs(k, sum):
    global res
    
    if sum == s:
        res += 1

    for i in range(k + 1, n):
        dfs(i, sum + arr[i])

 

위 코드를 0 ~ n - 1 번째 값을 시작으로 n번 실행한다.

 

import sys

def dfs(k, sum):
    global res
    
    if sum == s:
        res += 1

    for i in range(k + 1, n):
        dfs(i, sum + arr[i])
    
input = sys.stdin.readline
n, s = map(int, input().split())
arr = list(map(int, input().split()))
res = 0

for i in range(n):
    dfs(i, arr[i])

print(res)

 

파이썬 문제를 풀면서 전역변수의 구분이 궁금해졌다.

res도 arr도 외부에 있는 변순데 arr은 잘 작동되고, res는 global 키워드 없이는 오류가 났다.

이 부분은 찾아봐야겠다.