[BOJ] 1182 - 부분수열의 합

사용 언어: Python3

문제

백준 1182

내 풀이

첫 번째

N, S = map(int, input().split())
lst = [int(x) for x in input().split()]

cnt = 0
visited = [False] * N

def calcSum():
  tot = 0
  for i in range(N):
    if visited[i]:
      tot += lst[i]
  return tot

ans = 0
def dfs(idx, cnt, maxVal):
  global ans
  if cnt == maxVal:
    if calcSum() == S:
      ans += 1
  for i in range(idx, N):
    if visited[i]:
      continue
    visited[i] = True
    dfs(i, cnt+1, maxVal)
    visited[i] = False

for k in range(1,N+1):
  dfs(0,0,k) # 원소가 1개부터 N개까지 모든 부분수열 합 구하기

print(ans)

• 정답!
  • 하지만 시간이 6800ms나 걸린다.

다른 사람 풀이

백트래킹

N, S = map(int, input().split())
lst = [int(x) for x in input().split()]

ans, currentSum = 0, 0

def dfs(cur):
  global ans, currentSum
  if cur == N:
    return
  # 현재까지의 합이 S 이면 결과 +1
  if currentSum + lst[cur] == S:
    ans += 1

  # 이번 원소를 포함시키지 않고 시도
  dfs(cur + 1)

  # 이번 원소를 포함시키고 시도
  currentSum += lst[cur]
  dfs(cur + 1)

  # 마지막에 다시 이번 원소를 빼줘야 함
  currentSum -= lst[cur]

dfs(0) # 0번째 원소부터 방문
print(ans)

• 332ms로 성공!
• 각 방문마다 이번 원소를 포함시키고 다음 원소로 넘어가거나, 포함시키지 않고 다음 원소로 넘어가는 2개의 선택지를 탐색합니다.
  • 그렇게 탐색을 하면서 현재 합이 S가 될 때마다 전역변수 ans를 증가하면 모든 탐색이 끝나고서 ans가 결과가 됩니다.
• A번 정점의 DFS가 끝날 때마다 A번 정점을 방문하기 전 상태로 되돌려놔야 한다는 겁니다.
  • 이 코드의 경우는 다음 원소를 더해 본 뒤 탐색이 끝나면 다시 currentSum에서 그 원소를 빼서 원래대로 되돌리는 부분이 되겠습니다.
• 이렇게 가능한 모든 조합을 다 시도하는 것이 백트래킹이고, 대체로 반복문이 아니라 DFS를 가미한 재귀호출로 이루어지다 보니 예외상황이 발생하면 끊는 것도 중요합니다.
  • 참고로 위 문제의 시간복잡도는 각 원소를 포함/미포함한 모든 경우를 완전 탐색했으니 O(2^N)입니다. N이 작으니까 풀 수 있는 거죠.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기