[BAEKJOON]1182 부분수열의 합

문제 요약

• 알고리즘 분류: 백트래킹, 조
• 난이도: Silver2
• 문제내용:
  • 부분수열중 합해서 합이 S인 개수를 구하여라

• 사이트 주소: https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

문제풀이

 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다.

https://jih3508.tistory.com/84

[알고리즘 이론] 백트래킹(Backtracking)

접근 방법 

  이번 문제에서는 백트레킹에서 조합 구현만 하면 되는 문제이다. 구현하는 방법은 아래 같이 하면된다.

1. 개수 세는 변수를 0으로 초기화 한다.
2. 재귀 호출할 함수를 만든다.
   • 재귀 호출 파라미터를 배열을 위치와 중간에 더할 값을 각 각 0으로 시작한다. 배열의 시작 위치를 k 중간에 더하는 파라미터를 value로 한다.
   • K부터 시작해 N까지 반복문을 돌린다.
   • 반복문 i번째 더한다.
   • 파라미터 i + 1와 value로  재귀 함수 호출한다.
   • 재귀 호출후 k가 1이상 value가 S와 같은면 개수를 +1로 늘린다.
   • 재귀 호출후 k가 배열 크기와 같으면 return시칸다.

 조합 백트레킹 구현은 코드 아래와 같이 구현이 가능하기 때문에 외워두면 도움이 많이 될것이다.

Python

def combination(k = 0, value = 0):
    global count
    if(k > 0 and value == S):
        count += 1
    if(k == N):
        return
    else:
        for i in range(k, N):
            combination(i + 1, value + array[i])

Java

public static void combination(int k, int value) {
		
    if(k > 0 && S == value) {
        count ++;
    }
    if (k == N) {
        return;
    }else {
        for(int i = k; i < N; i++) {
            combination(i + 1, value + array[i]);

        }
    }
}

 

Code

Python

 파이썬으로 백트레킹으로 구현이 가능하지만 combination 외부 모듈에서 제공해주기때문에 2가지 방법으로 구현을 하는것을 보여 주겠다.

백트레킹

def combination(k = 0, value = 0):
    global count
    if(k > 0 and value == S):
        count += 1
    if(k == N):
        return
    else:
        for i in range(k, N):
            combination(i + 1, value + array[i])

N, S = map(int, input().split())
array = list(map(int, input().split()))
count = 0

combination()

print(count)

combination

from itertools import combinations

N, S = map(int, input().split())
array = list(map(int, input().split()))
count = 0

for i in range(1, N + 1):
    for arr in combinations(array, i):
        count += sum(arr) == S

print(count)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int[] array;
	static int count = 0;
	static int N, S;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		
		array = new int[N];
		st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		combination(0, 0);
		System.out.println(count);
	}
	
	public static void combination(int k, int value) {
		
		if(k > 0 && S == value) {
			count ++;
		}
		if (k == N) {
			return;
		}else {
			for(int i = k; i < N; i++) {
				combination(i + 1, value + array[i]);

			}
		}
	}
	
}