원형 수열 풀이

문제는

수열 {1, 1, 4, 7, 9} 가 있을 때
연속된 1개씩 더한 값: 1, 1, 4, 7, 9
연속된 2개씩 더한 값: 2, 5, 11, 16, 10
...
연속된 5개씩 더한 값: 22

했을 때 이 값들을 배열에 넣고, 중복된 수를 뺐을 때 총 몇 개인지를 반환하는 문제였다.

이 문제는 이중 벡터를 사용한 dp 방식으로 푸는 게 좋아보였다.

i, j 말고도 k를 사용해서 맨 뒷 숫자가 맨 앞 숫자와도 연결되도록 하는 것이 중요했다.

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

using namespace std;

int solution(vector<int> elements) {
    int answer = 0;
    set<int> numbers; // 합들을 여기 저장해두면 자동으로 겹치는 수는 없어짐
    int Size = elements.size();
    vector<vector<int>> dp(Size, vector<int>(Size));
    
    for(int i=0; i < elements.size(); i++)
    {
        dp[0][i] = elements[i];
        numbers.insert(dp[0][i]);
    }
    
    for(int i=1; i < elements.size(); i++)
    {
        for(int j=0, k=i; j<elements.size(); ++j, k = (k==Size-1)? 0 : ++k)
        {
            dp[i][j] = dp[i-1][j] + dp[0][k];
            numbers.insert(dp[i][j]);
        }
    }
    
    answer = numbers.size();
    
    return answer;
}

완전탐색으로 풀려고 했지만,
실무에서는 위 방식이 더 좋다고 하여 기록해본다.

<완전탐색 코드>

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

using namespace std;

int solution(vector<int> elements) {
    set<int> S;

    int n = elements.size();

    for (int i = 0 ; i < n ; ++i) {
        int sum = 0;
        for (int j = i ; j < i + n ; ++j) {
            sum += elements[j % n];
            S.insert(sum);
        }
    }

    return S.size();
}