[알고리즘] 1024. 수열의 합

---

0. 문제

 

1024번: 수열의 합

 

---

1. 제출

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n, l;

vector<int> find(){
    vector<int> vec;

    int cur = l;
    while(cur <= 100){
        bool flag = false;
        int div = n / cur;
        int left = n % cur;
        if(cur%2==1){
            if(left == 0){
                int d = (cur/2);
                for(int i = 0; i < cur; i++){
                    int tmp = div-d+i;
                    if(tmp < 0){
                        vec.clear();
                        cur++;
                        flag = true;
                        break;
                    }
                    vec.push_back(tmp);
                }
                if(flag) continue;
                return vec;
            }
        }else{
            if(left != 0 && left == cur/2){
                int d = (cur/2) - 1;
                for(int i = 0; i < cur; i++){
                    int tmp = div-d+i;
                    if(tmp < 0){
                        vec.clear();
                        cur++;
                        flag = true;
                        break;
                    }
                    vec.push_back(tmp);
                }
                if(flag) continue;
                return vec;
            }
        }
        cur++;
    }
    vec.push_back(-1);
    return vec;
}

int main(){
    cin >> n >> l;
    vector<int> vec = find();
    for(int i : vec)
        cout << i << " ";
    return 0;
}

어떻게든 풀었다.

 

주어진 예시를 바탕으로 규칙을 찾으려고 노력했다.

 

그 결과 조건을 만족하는 두 가지 경우를 찾을 수 있었다.

 

• 배열의 길이(cur)가 짝수이면서 n%cur이 cur/2인 경우
• 배열의 길이(cur)가 홀수이면서 n%cur이 0인 경우

 

이 두 가지 경우 중 하나를 만족하고 각각의 요소가 0보다 크거나 같은 정수로만 이루어진 리스트인 경우를 찾아야 한다.

 

나머지 경우의 수는 배열의 길이(cur)를 상승시키면서 다시 시도해 본다.

 

결론적으론 문제를 푸는 것에 성공했지만 풀면서도 잘못 풀고 있다는 것을 느끼고 있었다.

 

---

2. 개선

 

이 문제가 진정으로 요구하는 것은 따로 있었다.

 

문제를 재정의하자면 “주어진 조건을 만족하는 첫 번째 정수(a1)를 찾는 것”이 가장 중요했다.

 

등차수열의 합 공식을 변형하여 등차수열의 합(N)과 수열의 길이(L)로 이루어진 첫번째 정수(a1)에 관한 식으로 변형해야 한다.

• a1 >= 0인 정수
• N은 주어짐
• 2 <= L <= 100인 정수, 주어진 값부터 시작

 

N = L * a1 + (0 + L - 1)/2

        -> a1 = ((N - (L - 1)/2)/L

 

a1을 구하고 ... 

1. 0보다 크거나 같은지
2. 정수인지

확인한다.

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, L;
    cin >> N >> L;

    for (int length = L; length <= 100; ++length) {
        // a1 = (N -  constant) / L
                // 등차수열의 합 공식에서 상수 부분
        int constant = (length * (length - 1)) / 2;

                // a1은 0보다 크거나 같은 정수인가?
        if ((N - constant) % length == 0 && (N - constant) / length >= 0) {
            // 등차수열의 시작 값 계산
            int a1 = (N - constant) / length;

            // 길이가 100보다 작거나 같은 경우 출력
            if (length <= 100) {
                for (int i = 0; i < length; ++i) {
                    cout << a1 + i << " ";
                }
                cout << endl;
                return 0;
            }
        }
    }

    // 길이가 100보다 크거나 수열이 없는 경우
    cout << -1 << endl;
    return 0;
}

문제를 푸는 접근방식부터 잘못되었다.

 

수학적인 사고보다는 구현 자체에 집중했다.

 

앞으로는 문제를 수학적으로 표현하고 재정의하는 과정을 거쳐서 풀어야겠다.

(+꼭 손으로 쓰면서 문제를 풀자.)

 

---