[C++]백준 - 1024번 문제

1024번: 수열의 합 (acmicpc.net)

1024번: 수열의 합

 

1024번 : 수열의 합

---

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

입력

---

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

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

합해서 N을 만들 수 있는 최소 L의 길이를 가진 수열을 구하는 문제입니다.

 

우선 주어진 L의 길이 만큼, 수열의 합을 만듭니다.

 

이 때, 수열은 무조건 0으로 시작한다고 가정합시다.

 

그러면, 예제 1처럼 입력을 받았을 때

 

N = 18, L = 2 입니다.

 

그러면 가정한 수열은 {0, 1}이고, 합은 18이 됩니다.

 

만약 우리가 2의 길이를 가진 수열의 합으로 18을 나타낼 수 있다면 수열의 모든 원소에

 

같은 값을 더해주었을 때, 18을 만들 수 있어야합니다.

 

이 값을 X라고 가정하면, 우리가 구하고자 하는 수열은 {X, X+1}이 됩니다.

 

그런데, X + X + 1 = 18을 만족하는 음이 아닌 정수 X는 존재하지 않습니다.

 

풀어 보면, 2X = 17을 만족하는 X가 없기 때문입니다.

 

그렇다면, L = 2일 때, 18의 값을 만들 수 없으므로 우리는 L보다 긴 수열을 만들어야 합니다.

 

아까 처럼 수열의 길이를 하나 늘려 길이가 3인 수열을 만듭니다.

 

X + X + 1 + X + 2 = 18을 만족하는 X가 존재하면 정답입니다.

 

3X + 3 = 18 -> 3X = 15 -> X = 5일 때 만족합니다.

 

따라서 구하고자 하는 수열은 {5, 6, 7}이 정답입니다.

 

만약 계속 수열의 길이를 늘려 100을 넘기게 되거나, N의 크기가 너무 작다면 수열을 구할 수 없으므로

 

-1을 출력합니다. 

 

 

 

코드

---

#include <iostream>
using namespace std;

int main()
{
    int N, L;
    scanf("%d %d", &N, &L);
    
    int summ = 0;
    for(int i = 0; i < L; i++) summ += i;
    bool possible = false;
    while(L <= 100)
    {
        //최소 수열보다 작을 때
        if(N < summ) break;
        //수열을 찾음
        if((N - summ) % L == 0)
        {
            possible = true;
            int X = (N - summ) / L;
            
            for(int i = 0; i < L; i++) printf("%d ", X + i);
            break;
        }
        summ += L;
        L++;
    }
    
    if(!possible) printf("-1");
    return 0;
}

 

그 외

---