728x90
반응형
문제 바로가기
문제:
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력:
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
풀이:
1.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N, S = map(int,sys.stdin.readline().rstrip().split(" "))
arr = list(map(int,sys.stdin.readline().rstrip().split(" ")))
cnt = 0
res = []
def solution(idx):
global cnt
if sum(res) == S and len(res) > 0:
cnt += 1
for i in range(idx,N):
res.append(arr[i])
solution(i+1)
res.pop()
solution(0)
print(cnt)
그 전에 N과M때 하던 방식
2.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N, S = map(int,sys.stdin.readline().rstrip().split(" "))
arr = list(map(int,sys.stdin.readline().rstrip().split(" ")))
cnt = 0
def solution(num, sum):
global cnt
if num >= N: # 수열의 끝까지 도달하면 종료
return
sum += arr[num] # 현재 원소를 더함
if sum == S: # 원소의 합이 S와 같다면 경우의 수 증가
cnt += 1
solution(num + 1, sum) # 다음 원소를 더하는 경우
solution(num + 1, sum - arr[num]) # 다음 원소를 더하지 않는 경우
solution(0, 0) # 재귀 함수 호출, 초기값은 0으로 설정
print(cnt) # 결과 출력
요즘 내가 쓰는 방식
solution에 2개가 있는건
다음 숫자를 선택했을때.
다음 숫자를 선택하지 않았을때를 나눠서 하는것이다.
result = []
def solution(num, total):
global cnt,res,result
if num == N:
if total == S and len(result)>0:
cnt += 1
return
result.append(arr[num])
res += arr[num]
solution(num+1, res)
res -= arr[num]
result.pop()
solution(num+1, res)
solution(0, 0)
print(cnt)
또 이런 방법도 있다.
이건 저번에 치킨배달 문제를 쓸때 푼 방법인데. 조합의 수를 재귀로 나타내는것이다.
굳이 몰라도 될거같다.
반응형
댓글