백 준 - 1182

 

문제 : www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

문제는 다음과 같습니다.

 

문제의 조건은 주어진 수열에서 부분 수열을 뽑아서 합이 S가 되는 경우를 모두 찾는 것입니다.

모든 경우를 검사하는 것으로 제귀적인 방법을 이용해서 구현을 해보았습니다.

경우는 해당 수를 선택하는가? , 선택하지 않는가? 로 2가지로 나누어서 진행을 하며 합이 S가 되면 경우를 증가시키도록 하였습니다.

 

전체적인 코드는 다음과 같습니다.

import java.util.*;

public class Main {

    // 문제 1182

    public static int caseValue = 0;

    public static void main(String[] args) {

        Scanner stdin = new Scanner(System.in);

        int n = stdin.nextInt();
        int s = stdin.nextInt();

        int[] arr = new int[n];

        for (int i = 0 ; i < arr.length ; i++) {

            arr[i] = stdin.nextInt();
        }

        LinkedList<Integer> list = new LinkedList<>();
        boolean flag = false;

        getSubSequence(arr , 0 , list , s , flag);

        System.out.println(caseValue);

    }

    public static void getSubSequence(int[] arr , int idx , LinkedList<Integer> list , int value , boolean flag) {

        if (getSum(list) == value && flag == true) { //문제의 요구 만족

            caseValue += 1;
        }

        if (idx >= arr.length) { // 종료조건

            return;
        }

        // 해당 항을 부분 수열에 선택하고 다음 항 으로 진행
        list.add(arr[idx]);
        getSubSequence(arr , idx+1 , list , value , true);

        //해당 항을 선택하지 않고 다음 항 으로 진행
        list.removeLast();
        getSubSequence(arr , idx+1 , list , value , false);

    }

    public static int getSum(LinkedList<Integer> list) {

        int sum = 0;

        for (int i = 0 ; i < list.size() ; i++) {

            sum += list.get(i);
        }

        return sum;
    }
}

 

주의할 부분은 왜 boolean형 변수 flag를 만들어서 제귀에 이용하나 인 것인데 그 이유는 제가 만든 제귀함수에 있어서는 flag 처리를 하지 않으면 합이 S가 되는 부분 수열을 가진 배열에서 다음 항을 추가하지 않았을 때 해당 배열의 합은 그대로 S이기 때문에 경우가 의도치 않게 추가가 된다는 것입니다. 

 

이러한 이유로 인해서 flag형 변수를 만들어서 제귀함수의 입력으로 넣어줍니다.