[C++] BJO 1024 : 수열의 합

문제

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

 

 

 

 

 

풀이

입력받은 n/2+1 부터 수를 1씩 줄여가며 더해가고, n을 만들 수 있는지를 검사한다.

이때 가장 오래전에 더한 수를 end에 저장하고, 가장 최근에 더한 수를 start에 저장한다.

만약 새로 계산한 합이 n을 넘었다면, end를 합에서 빼준 후 end를 줄여준다.

 

자세한 구현은 코드에서 확인 가능하다.

 

 

 

코드

#include <iostream>
using namespace std;

long n, l;
long ans = 1000;
int main()
{
    cin >> n >> l;

    long end = n/2 + 1;
    long start = end-1;
    long cnt = end;
    while(end > start && end >= 0 && start >=0){
        cnt+= start;
        
        if(cnt == n && end-start+1 >= l){
            ans = end - start + 1;
            break;
        }
        
        if(cnt > n){
            cnt-= end;
            end--;
        }
        start--;
    }
    
    
    if(ans == 1000 || ans >100) cout << -1;
    else{
        for(int i = start; i<=end; i++ )cout << i << " ";
    }
    
    cout << "\n";
    return 0;
}

 

 

 

---

메모

완전탐색이 아니어도 풀리기는 풀린다. 
그리고 좀 더 수학적으로 접근하는 방법이 있기는 한데, 그걸 떠올리기 싫었고 더 복잡해보여서 이렇게 풀었다.
아 대신 내 코드의 경우 처음에 95%에서 틀리는 문제가 반복되었는데 이는 처음 start와 end를 초기화하는 과정에서 고려하지 못한 케이스가 있었다.


지금은 end를 n/2+1로 설정하지만 이전에는 1을 더하지 않아서 7+8=15와 같은 경우를 고려하지 못했다. 
반례로 참고해보아도 좋을 듯하다.