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

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

프로그래머스

 

---

 

문제 해결 과정

착안

길이가 $n$인 원형 수열이 주어졌을 때, 각각의 요소에 대하여 길이가 1, 2, $\cdots, n$ 인 부분 수열의 합을 동적계획법(dynamic programming)을 활용해 구한 다음 중복되지 않는 합들의 갯수를 센다. 

 

구현

중복되지 않는 부분 수열의 합들의 갯수를 세기 위해 std::unordered_set<> 클래스를 활용하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <vector>
#include <unordered_set>

using namespace std;

int solution(vector<int> elements)
{
    unordered_set<int> nums;
    for (int i = 0; i < elements.size(); i++)
    {
        int num = 0;
        for (int j = 0; j < elements.size(); j++)
        {
            num += elements[(i + j) % elements.size()];
            nums.emplace(num);
        }
    }
    
    return nums.size();
}

 

실행 결과