[백준] 1024 번 : 수열의 합 / C++

[문제]

https://www.acmicpc.net/problem/1024

1024번: 수열의 합

문제 :

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.

 

입력 : 

 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

출력 :

 만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100보다 크거나 그러한 수열이 없을 때는 -1을 출력한다.

[코드 풀이]

[실패한 코딩]

처음에는 배열로 누적합 만들려 했더니 수의 범위가 엄청나서 C++ 배열 크기 제한을 넘어서 Seg Fault 떠서 벡터로 바꿨더니,

이번에는 너무 느리다~~~~ 값은 잘 나오는데...

#include <iostream>

using namespace std;
int N = 500000000;
//배열에다가 누적합 넣으려 했더니 배열 크기 제한에 걸린다.
//벡터로 가자.

int finder(vector<int> vec, int x,int y){ //주어진 합을 만드는 연속 수열의 시작 인덱스 반환.
    int i=0;
    while(x!=vec[i+y]-vec[i]){
        if(i+1>(x/2)){
            y++;
            i=0;
        }
        if(y>100){
            i=-1;
            break;
        }
        i++;
    }
    return i;
}
int finder_serial(vector<int> vec, int x,int y){ //최소 연속되는 갯수 반환
    int i=0;
    while(x!=vec[i+y]-vec[i]){
        if(i+1>=(x/2)){
            y++;
            i=0;
        }
        if(y>100){
            i=-1;
            break;
        }
        i++;
    }
    return y;
}

int main() {
    int sum;//연속되는 수열의 합이 뭐여야 하는데?
    int serial_killer;//얼마나 연속되나?
    int ans;
    cin >> sum >> serial_killer;
    cout << "엥?" << '\n';
    vector<int> fixvec;
    cout << "엥?" << '\n';
    fixvec.reserve(N);

    for(int i=0; i<N;i++){
       fixvec.push_back(i);
    }
    vector<int> prefix;
    cout << "엥?" << '\n';
    prefix.push_back(0);
    prefix.reserve(N);
    for(int i=1; i<N;i++){
       prefix.push_back(prefix[i-1]+fixvec[i]);
    }
    cout << "엥?" << '\n';
    int less_serial;
    int foundIndex;

    foundIndex = finder(prefix,sum,serial_killer);
    less_serial = finder_serial(prefix,sum,serial_killer);
    for(int i =0; i< less_serial;i++){
        if(foundIndex!=-1){
            cout << foundIndex+1+i << " ";
            continue;
        }
        cout << -1 <<'\n';
        break;
    }
    //cout << ans << '\n';
    

}

 좀 빠르게 만들긴 했지만, 이번에는 메모리 초과이다.

정답이지만, 메모리를 초과.

 

 아무래도 128 MB 제한인데 int 4바이트에 누적합 배열 만든다고 1,000,000,000을 하니 약 400MB 정도로 보기 좋게 메모리를 초과시켰다. 다른 방법을 찾아야겠다.

 

누적합으로 풀려는 건 틀렸다.

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


using namespace std;
//배열에다가 누적합 넣으려 했더니 배열 크기 제한에 걸린다.
//벡터로 가자.

void finder(vector<int> vec, int x,int y){ //주어진 합을 만드는 연속 수열의 시작 인덱스 반환.
    int i=0;
    while(x!=vec[i+y]-vec[i]){
        if(i>(x/2)){
            y++;
            i=1;
        }
        if(y>100){
            i=-1;
            break;
        }
        i++;
    }
    for(int k = 0; k< y;k++){
        if(i!=-1){
            cout << i+k << " ";
            continue;
        }
        cout << -1 <<'\n';
        break;
    }
}
int main() {
    int sum;//연속되는 수열의 합이 뭐여야 하는데?
    int serial_killer;//얼마나 연속되나?
    int k=1;
    cin >> sum >> serial_killer;

    int cosum=sum/2+1;
    vector<int> prefix;
    prefix.push_back(0);
    prefix.push_back(0);
    prefix.reserve(cosum);
    for(int i=2; i<cosum;i++){
       prefix.push_back(prefix[i-1]+k);
       k++;
    }

    finder(prefix,sum,serial_killer);

}

 그래서 아래 코드는 그냥 for문으로 간단하게 구현해보았다.

근데 시간 초과. 어쩌라는거야아아아아

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


using namespace std;

int main() {
    int sum;//연속되는 수열의 합이 뭐여야 하는데?
    int serial_killer;//얼마나 연속되나?
    int k=1;
    cin >> sum >> serial_killer;
    int cosum=sum/2+1;
    int temp=0;
    int i=0;
    while(temp!=sum){
        if(serial_killer>100){
            i=-1;
            break;
        }else{
            for(i=0; i< cosum; i++){
                for(int j=0; j<serial_killer;j++){
                    temp += i+j;
                }
                if(sum==temp){
                    break;
                }else{
                    temp=0;
                }
            }
            serial_killer++;
        }
        
    }
    if(i!=-1){
        for(int j=0;j<serial_killer-1;j++){
        cout << i+j << ' ';
        }
    }else{
        cout << i << '\n';
    }
    
}

 아래는 좀 더 최적화했다. 근데.. 그래도.. 시간은 초과.

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


using namespace std;

int main() {
    int sum;//연속되는 수열의 합이 뭐여야 하는데?
    int serial_killer;//얼마나 연속되나?
    int k=1;

    cin >> sum >> serial_killer;
    
    int cosum=sum/2+1;
    int temp=0;
    int i=cosum;
    while(temp!=sum){
        if(serial_killer>100||i<serial_killer){
            //cout << i << '\n';
            i=-1;
            break;
        }else{
            //cout << "여기" << '\n';
            for(i=sum/serial_killer+serial_killer; i>0; i--){
                for(int j=0; j<serial_killer;j++){
                    temp += i-j;
                }
                if(sum==temp){
                    break;
                }else{
                    temp=0;
                }
            }
            if(sum==temp){
                break;
            }
            i=cosum;
            serial_killer++;
        }
    }
    //cout << i << '\n';
    if(i+1<serial_killer){
        i=-1;
    }
    //cout << i <<'\n';
    if(i!=-1){
        for(int j=serial_killer-1;j>-1;j--){
        cout << i-j << ' ';
        }
    }else{
        cout << i << '\n';
    }   
}

  

[성공한 코딩]

 

위의 것에서 더 최적화 했다.

 

굳이 for문으로 확인 안 해도 되는 부분을 잘라내도록 if문을 만들었다.

결과는 성공적. 시간복잡도를 머리카락 자르듯이 잘랐다. 코드의 수행방식 자체를 바꾼 것은 아니라서 알고리즘.. 최적화..? 라고 하기엔 그렇고 수학적 문제를 해결한 것 같다.

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


using namespace std;

int main() {
    int sum;//연속되는 수열의 합이 뭐여야 하는데?
    int serial_killer;//얼마나 연속되나?
    int k=1;

    cin >> sum >> serial_killer;

    int temp=0; //연속된 합을 저장하고 비교하는 데 사용하는 변수
    int i=sum/serial_killer+serial_killer; //합에서 연속되는 개수로 나누고, 다시 연속되는 개수로 더해주기.
    //이건 굳이 계산 안 해도 되는 부분을 처리하기 위해서, 저것보다 그 이상인 값은 연속 합 확인해도 무조건 sum보다 크다.

    while(temp!=sum){
        if(serial_killer>100||i<serial_killer){//연속이 100을 넘거나, 인덱스보다 연속 개수가 크면 음수까지 갈 경우
            i=-1;
            break;
        }else{
            for(i=sum/serial_killer+serial_killer; i>0; i--){//저 값부터 줄여나가면서 확인하자.
                for(int j=0; j<serial_killer;j++){//연속되는 수를 각각 temp에 더해주기.
                    temp += i-j;
                }
                if(temp<=sum){//sum과 같으면 멈춰서 인덱스를 확인하고
                    break; //sum보다 temp가 작으면 그 이후의 for문을 돌아도 여전히 temp가 작은 결과만 나오니까 브레이크
                }else{
                    temp=0; //다시 0으로 바꿔서 연속되는 수를 더할 준비를 하자.
                }
            }
            if(sum==temp){
                break;//정답이 나왔으니 반복문을 나오자.
            }
            i=sum/serial_killer+serial_killer;//다시 반복문 돌릴 준비하는 것이다.
            serial_killer++; //연속 개수를 더 늘려서 반복문을 돌릴 차례.
        }
    }

    if(sum==0&&i==1){ //위 while문이 제대로 돌지 않는 유일한 예외
        cout << 0 <<'\n';
        return 0;
    }

    if(i+1<serial_killer){ //이건 음수까지 셀 경우라서 제외.
        i=-1;
    }

    if(i!=-1){ //출력
        for(int j=serial_killer-1;j>-1;j--){
        cout << i-j << ' ';
        }
    }else{
        cout << i << '\n';
    }   
}

 

 

 

[후기 및 배운 점]

선배가 투 포인터를 사용하라고 하셨다. 다음에 그걸로 이걸 해결해보아야겠다.

 

 압도적으로 범위가 넓으면 누적합 배열을 만들 경우 메모리 초과가 난다는 것을 알았다. 그렇다고 그냥 하자니 시간 초과가 나타나는 경우가 생기고, 이건 진짜 알고리즘 해결이라기보다 수학적 규칙을 찾아서 해결한 느낌이다.