[알고리즘풀이]백준 1182 : 부분수열의 합 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번 알고리즘 스터디에서 JAVA를 이용해 백준 1182번 부분수열의 합을 풀게 되었습니다.

1182번: 부분수열의 합

본문

1) 문제

백준 1182번 부분수열의 합은 bruteforce algorithm입니다.

 

2) 과정

이 문제는 메모리 초과, 시간 초과 등 여러 고전을 거쳐 풀었던 문제입니다...

저번에 풀었던 15649의 n과 m문제와 비슷해 그 형태를 유지하려고 하다보니 불필요하게 함수가 많아졌기도 하고, 

무작정 다 더해서 값을 구하고 분류하려했더니 오답 처리가 자꾸 나왔습니다.

15649번: N과 M (1)

 

각설하고 코드 설명을 하자면, 이전엔 input, func, output 삼단 구조를 고집하다가 후반엔 다 정리하고 보기 좋게만 하면 되는거지 꼭 틀에 얽매일 필요없다 생각해 input과 func로만 구성했습니다.

 

2-1) main

    public static void main(String[] args) throws IOException {
        input();
        func(new int[n], 0);
        if(s==0) count--;
        System.out.println(count);
    }

main은 다음과 같습니다.

먼저 input()으로 함수를 읽어오고 func에 input에서 받은 n만큼의 int배열을 만들어 첫번째 파라미터로 넣어주고, 초기 index를 의미하는 0을 두번째 파라미터로 넣어줍니다. 그리고 if(s==0) count--는 후에 내용을 보면 자세히 이해하기 쉬울 것 같은데요. 이는 배열로 만들어야하는 값인 S가 0인경우 모든 값의 경우가 0일 때인 공집합일 때를 고려해야 하기에 count--를 해준 것입니다. 그렇게 최종적으로 count를 출력하며 main함수는 끝이납니다.

 

2-2 ) input()

    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] strArrFirst = reader.readLine().split(" ");
        n = Integer.parseInt(strArrFirst[0]);
        s = Integer.parseInt(strArrFirst[1]);

        String[] strArrSec = reader.readLine().split(" ");
        intArr = new int[n];
        for(int i =0;i<n;i++) intArr[i]=Integer.parseInt(strArrSec[i]);
        Arrays.sort(intArr);

        count=0;

    }

 

 

[개념정리] System.in / InputStreamReader / BufferedReader 정리

 위에 글처럼 bufferedReader객체의 readLine으로 받아온 String을 String객체의 내장함수인 split함수를 통해 " " 단위로 쪼개 String[]인 strArrFirst에 담아줍니다. 그리고 첫줄엔 숫자의 개수인 N과 수열로 만들고자하는 값 S 가 차례대로 적혀있기 때문에 string인 각각을 Integer.parseInt로 바꾸어줍니다. 

 그리고 두번째 문단에서도 마찬가지로 " " 로 구분해 String을 읽고 이를 각각 숫자로 바꿔 intArr에 저장해줍니다. 그리고 Arrays의 함수인 sort를 이용해 간단하게 배열을 정렬시켜줍니다. 

 마지막 세번째 문단에서 count=0은 수열의 합이 S를 만족시키는 경우의 수를 나타내는 count를 초기설정 해준것입니다.

 

2-3) func(int[] ints, int index)

 private static void func(int[] ints, int index) {
        if (index == n) {
            int sum = 0;
            for (int j = 0 ; j<ints.length;j++) {
                sum += ints[j];
            }
            if (sum == s){
                count++;
            }
        }else{
            // include
            ints[index]=intArr[index];
            func(ints, index+1);

            // include X
            ints[index]=0;
            func(ints, index+1);
        }

    }

 

저는 기본적으로 재귀함수를 꽤 선호하는 편입니다. 재귀를 잘만 이용하면 여러번 반복된 값을 안적어도 충분히 원하는 값을 만들 수 있기 때문인데요. 해당 func에서도 탈출조건인 index==n이 되지않으면 해당 index의 경우를 포함하든지 안포함하든지로 나눠 재귀를 돌게됩니다.

 

이번 문제의 중요 로직이자 해당 함수의 원리는 구현시 그렸던 이 그림을 보면 알 수 있습니다.

앞서 말했듯이 해당 index의 값을 포함하는 경우와 포함하지 않는 경우로 구분해, 값을 포함한다면 ints라는 함수에 해당 값을 넣어 넘겨주고, 아니라면 0을 넣어 넘겨줍니다. 사진에서는 input에서 정렬을 했기 때문에 index에 따라 -7, -3, -2, 5, 8의 값이 들어가거나 0이 들어가 최종적으로는 32(2의 n승개의 경우가 나옴)개의 경우를 살펴보게 되는 것입니다.

 

그렇다면 index가 n이 된다는건 다들 아시겠지요? 모든 값을 다 넣었고 그 다음값(위의 사진이면 6번째 회전)을 다룰 때를 의미합니다. 이때는 ints에 담아온 값들을 모두 더해 sum과 같다면 count를 증가시켜줍니다. 그리고 아니라면 그 전 index로 가서 include X인 경우로 넘어가게 되는 것이지요! 순서를 정리하면 다음처럼 그려볼 수 있겠네요!

 

 

3) 전체 코드

그렇게 완성된 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    private static int n,s;
    private static int[] intArr;

    private static int count;

    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] strArrFirst = reader.readLine().split(" ");
        n = Integer.parseInt(strArrFirst[0]);
        s = Integer.parseInt(strArrFirst[1]);

        String[] strArrSec = reader.readLine().split(" ");
        intArr = new int[n];
        for(int i =0;i<n;i++) intArr[i]=Integer.parseInt(strArrSec[i]);
        Arrays.sort(intArr);

        count=0;

    }

    private static void func(int[] ints, int index) {
        if (index == n) {
            int sum = 0;
            for (int j = 0 ; j<ints.length;j++) {
                sum += ints[j];
            }
            if (sum == s){
                count++;
            }
        }else{
            // include
            ints[index]=intArr[index];
            func(ints, index+1);

            // include X
            ints[index]=0;
            func(ints, index+1);
        }

    }

    public static void main(String[] args) throws IOException {
        input();
        func(new int[n], 0);
        if(s==0) count--;
        System.out.println(count);
    }

}

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/bruteforce/BOJ1182.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비