연속 부분 수열 합의 개수

작성일: 2024-11-04

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/131701

접근 방식

조합을 이용해서 풀 수 있는 문제다.

일반적으로 조합의 개수가 주어지고, 조합의 수를 구하는 반면

이 문제는, elements의 길이만큼의 조합의 수를 통해 해결해야 한다.

결과

소스 코드

import java.util.*;

class Solution {
    static Set<Integer> set = new HashSet<>();
    static int count = 0;
    public int solution(int[] elements) {
        for(int i=1; i<=elements.length; i++){
            for(int j=0; j<elements.length; j++){
                comp(0, 0, i, elements, j);
            }
        }
        return set.size();
    }

    void comp(int sum, int cnt, int target, int[] elements, int start){
        if(cnt==target){
            set.add(sum);
            return;
        }
        int idx = (start+1) % elements.length;
        comp(sum+elements[idx], cnt+1, target, elements, idx);
    }
}

조합의 일반적인 풀이 방법인 재귀를 통해 문제를 해결했다.

다만 elements의 길이가 최대 1000까지 주어지다보니, 실행시간이 최대 약 6초까지 나오기도 했다.

다른 접근 방식

dp를 이용한 풀이가 있었다.

처음 원소를 시작으로 하나씩 더 해가면서 조합을 통해 발생한 합을 set 자료구조에 더해가는 방식이다.

이런 방식을 사용할 경우, 시간 복잡도는 최대 O(n^2)로, 100만정도가 나오기 때문에

내 방식보다는 훨씬 빠르고 좋은 방식이다.

프로그래머스 실행 결과 기준, 최대 속도가 약 40배 차이났다.

import java.util.*;

class Solution {
    static Set<Integer> set = new HashSet<>();
    public int solution(int[] elements) {
        int dp[] = new int[elements.length];
        for(int i=1; i<=elements.length; i++){
            for(int j=0; j<elements.length; j++){
                dp[j]+=elements[(i+j-1) % elements.length];
                set.add(dp[j]);
            }
        }
        return set.size();
    }

}

알게 된 점

조합을 통해 모든 조합을 직접 반복 계산하여 구할 수 있겠지만,

조합의 특성상 한 번만 계산이 되었다면, 이후에는 중복으로 할 필요가 없는 것을 이용해서

이전 조합의 합을 따로 저장해두었다가 필요할 때 사용하여 자원을 절약할 수 있다.

dp적 사고 up