1. 부분수열의 합
- 난이도
- 실버2
- 시간 제한
- 2초
- 메모리 제한
- 256MB
- 출처
A. 📜 문제
위 백준 사이트에 접속하여 문제를 확인해주세요.
B. 💡 내 답안
a. 😅 1차 시도 (실패)
- dfs 함수 안에 dfs를 한번만 호출하는 방식으로 가능할줄알고 시도하다가 머리가 너무 복잡해져서 실패했다.
b. 😊 2차 시도 (성공)
def dfs(arr, result, i, s):
global count
if i >= len(arr):
return
result += arr[i]
if result == s:
count += 1
dfs(arr, result - arr[i], i+1, s)
dfs(arr, result, i+1, s)
global count
n, s = list(map(int, input().split()))
array = list(map(int, input().split()))
result = 0
count = 0
dfs(array, result, 0, s)
print(count)
c. 😊 3차 시도 (성공 - global 변수 개선)
def dfs(arr, result, i, s):
temp = 0
if i >= len(arr):
return 0
result += arr[i]
if result == s:
temp += 1
temp += dfs(arr, result - arr[i], i+1, s)
temp += dfs(arr, result, i+1, s)
return temp
n, s = list(map(int, input().split()))
array = list(map(int, input().split()))
result = 0
count = 0
count += dfs(array, result, 0, s)
print(count)
d. 🙄 회고
반성
- dfs를 할줄안다고 자만했었다.
결론
- 더 많이 해봐야지
C. 🧐 문제 해설
이해한 내용을 바탕으로 작성했습니다.
구조는 이런식으로 만들어진다.
순방향으로 쭉 더해지는 것과 한칸 건너뛰고 쭉 더해지는 것을 고려해야한다.
이 과정을 result - arr[i]로 구현한 이유는, 초기값 0은 계산되어서는 안되기 때문이다. 단순히 순방향으로 더해지는 것과 한칸 건너뛰고 더해지는 방식으로 구현하면, 반드시 초기값이 0인 지점으로 오게된다. 그럼, 만약 목표값이 0이라면, 카운트가 계속 증가하게 된다.
그래서, 처음에 arr[0]을 더하고 목표값인지 판별한 이후에 result - arr[0]와 i+1을 dfs 인자값으로 호출하여, 다음 값을 계산하였다.
참고문헌
baekjoon. 1182번: 부분수열의 합 (acmicpc.net). Baekjoon. (accessed Dec 6, 2021)
Ghost