[2025.02.24] 연속 부분 수열 합의 개수

문제 설명

철호는 수열을 가지고 놀기 좋아합니다. 어느날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합을 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4]로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.

원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

제한사항

• 3<=elements의 길이<=1,000
• 1<=elements의 원소<=1,000

 

 

입출력 예

elements			result	설명
[7, 9, 1, 1, 4]			18	길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다. 길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다. 길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다. 길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다. 길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다. 이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다. [1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(vector<int> elements) {
    int answer = 0;
    set<int> myset;
    int sum;
    
    // 길이 업데이트
    for(int i=0; i<elements.size(); i++)
    {
        // 부분수열의 첫 자리 업데이트
        for(int j=0; j<elements.size(); j++)
        {
            sum=0; // 초기화
            // 길이만큼 부분 수열 합 구하기
            for(int k=j; k<j+i; k++)
            {
                sum+=elements[k%elements.size()];
            }
            myset.insert(sum); // 부분 수열 합 저장
        }
    }
    answer=myset.size(); // 부분 수열 합 개수
    
    return answer;
}

이렇게 풀어도 괜찮은 건지는 잘 모르겠지만 일단 반복문 3개로 문제를 풀 수 있었다.

 

세 가지 역할을 하는 반복문이 필요하다.

1. 연속 부분 수열의 길이를 업데이트하는 반복문
2. 연속 부분 수열의 첫 원소를 업데이트하는 반복문
3. 길이 만큼 첫 원소부터 순서대로 연속 부분 수열의 합을 계산하는 반복문

아무리 생각해도 이 세 가지의 반복문이 필요했다.

 

첫째(i), 가장 큰 반복문은 연속 부분 수열의 길이를 업데이트하는 반복문이다. 길이가 0부터 elements의 길이-1까지 바뀔 수 있도록 해주었다. 부분 수열의 첫 원소부터 얼마나 뒤에 원소 까지 볼 것인지를 정하는 것이기 때문에 1부터가 아닌 0부터 세도록 하였다.

둘째(j), 중간 반복문은 연속 부분 수열의 첫 원소를 업데이트 하는 반복문이다. 수열의 시작을 어디로 할 것인지를 정하는 것이다.

셋째(k), 가장 안쪽의 반복문은 중간 반복문에서 정한 연속 부분 수열의 첫 원소(j번째 원소)부터 가장 큰 반복문에서 정한 수열의 길이(i)까지의 합을 계산한다. 반복문 안에서 elements의 원소들을 더하는데 추가적으로 설정해주어야 하는 것은 원형 수열에서의 움직임이다. 마지막 원소 다음의 index가 나오면 다시 0번째 원소로 돌아가야하기 때문에 elements.size()로 k를 나머지 연산해주었다.

 

마지막으로 set 컨테이너에 부분 수열의 합을 저장한다. 문제에서 반복을 제외하라고 하여 set을 선택하였다. 모든 반복문이 끝나고 set의 원소의 개수를 answer에 저장하고 반환하면 된다.

 

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스