문제 131701. 연속 부분 수열 합의 개수

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2 

 

문제 요약 설명

 원형 수열이란 아래 그림과 같이 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 아래 그림은 수열 [7, 9, 1, 1, 4]로 만든 원형 수열입니다.

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

입력

• 원형 수열의 모든 원소 elements

입력 제한

• 3 ≤ elements의 길이 ≤ 1,000
• 1 ≤ elements의 원소 ≤ 1,000

입력 예제

// input
[7,9,1,1,4]

// ans
18

 

풀이 방식

브루트 포스방식을 사용했다. elements의 길이가 1,000밖에 되지 않기 때문에 O(n^2)방식을 사용해도 1,000,000번 밖에 연산횟수가 나오지않아 시간초과가 발생하지 않는다. 따라서

• elements의 0부터 다음 elements.size()개의 원소들을 더해가며 연속 부분 수열의 합들을 map자료구조인 m에 저장
• elements의 1부터 elements.size()개의 원소들을 더해가며 연속 부분 수열의 합들을 map자료구조인 m에 저장
• ...
• elements의 elements.size()-1부터 elements.size()개의 원소들을 더해가며 연속 부분 수열의 합들을 map자료구조인 m에 저장하며 나올 수 있는 모든 종류의 합들을 저장한다.

정답은 m의 size이므로 m의 size를 answer에 저장하면 된다.

 

+) 아래 코드에서 elements_size가 아니라 elements_size-1인 이유는 모든 원소의 합들이 중복되서 계산되기 때문. 그래서 마지막에 추가적으로 모든 원소의 합을 구해주는 방식으로 변경하였다(굳이 이렇게 안해도 정답은 똑같다.)

 

정답 코드 

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<int> elements) {
    int answer = 0;
    map<int, int> m;
    
    int sum;
    int elements_size = elements.size();
    for(int i = 0; i < elements_size; i++){
        sum = 0;
        for(int n = 0; n < elements_size -1; n++){
            sum += elements[(i + n) % elements_size];
            m[sum]++;
        }
    }
    
    sum = 0;
    for(int elem : elements){
        sum += elem;
    }
    m[sum]++;
    
    answer = m.size();
    
    return answer;
}