[BOJ] 1024_수열의 합

수열의 합

문제 링크: https://www.acmicpc.net/problem/1024

1024번: 수열의 합

문제를 읽고 N과 M의 연관성을 찾게 되었다.
N을 M으로 나누고 그 근방의 리스트의 합이 N과 유사한 값을 내고 있음을 찾았다.

따라서, 먼저 손으로 20부터 23까지의 4개의 수 리스트를 한번 작성해 보았다.

예제

N
M -> N/M
List : Sum

20
3 -> 6
5 6 7 : 18
4 -> 5
4 5 6 7 : 22
5 -> 4
3 4 5 6 7 : 25
6 -> 3
1 2 3 4 5 6 : 21

21
2 -> 10
10 11 : 21
3 -> 7
6 7 8 : 21
4 -> 5
4 5 6 7 : 22
5 -> 4
2 3 4 5 6 : 20
6 -> 3
1 2 3 4 5 6 : 21

22
2 -> 11
11 12 : 23
3 -> 7
6 7 8 : 21
4 -> 5
4 5 6 7 : 22
5 -> 4
3 4 5 6 7 : 25
6 -> 3
1 2 3 4 5 6 : 21

23
2 -> 11
11 12 : 23
3 -> 7
6 7 8 : 21
4 -> 5
4 5 6 7 : 22
5 -> 4
2 3 4 5 6 : 20
6 -> 3
1 2 3 4 5 6 : 21

M이 주어지면 해당 값부터 1씩 증가시켜 리스트의 합과 N을 비교한다.

음이 아닌 정수의 리스트이므로 첫 시작점이 음수일 경우는 아무런 작업을 하지 않고 다음 단계인 M+1의 작업을 수행한다.

정답코드

#include<iostream>
using namespace std;

int sumList(int n, int m_) {
    int m = m_; //idx

    while (m<=100) {
        int sum = 0;
        int half;

        if (m % 2)
            half = m / 2;
        else
            half = (m- 1) / 2;

        int mid = n / m;
        int start = mid - half;


        if (start >= 0)
            for (int i = 0; i < m; i++)
                sum += (start + i);

        if (sum == n)
            return m;
        m++;
    }
    return -1;
}

void print(int n, int idx) {
    int half;

    if (idx % 2) 
        half = idx / 2;
    else
        half = (idx - 1) / 2;

    int mid = n / idx;
    int start = mid - half;

    for (int i = 0; i < idx; i++)
        cout << (start + i) << " ";
}

int main() {
    int n, m;
    cin >> n >> m;

    int idx = sumList(n, m);

    if (idx == -1)
        cout << -1 << endl;
    else
        print(n, idx);

    return 0;
}