[BOJ] 1024 : 수열의 합 - travelbeeee

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

---

[ 알고리즘풀이 ]

 합이 N이 되는 i개의 연속된 음이 아닌 정수들을 생각해보면, i 가 홀수냐 짝수냐에 따라 상황이 달라진다.

 먼저, i 가 홀수이면 다음과 같이 ..., K - 2, K - 1, K , K + 1, K + 2, ... 꼴을 이루게 되고 총 합이 K의 배수가 된다. 또, K는 (N / i) 가 되고, 시작하는 수는 (N / i) - ( i / 2)가 된다. 예를 들어 21을 3개로 포현하려면 중간 수 K = 21 / 3 인 7이 성립하고, 시작하는 수는 7 - (3 / 2)인 6이 성립한다.

 다음으로 i가 짝수일 때는 예시를 통해서 규칙을 캐치하면 훨씬 쉽다. i = 2일 때 우리가 얻을 수 있는 배열에 대해서 생각해보면 (1, 2), (2, 3), (3, 4) ... 등 N이 홀수이고 (N % i) == ( i / 2) 가 성립하는 것을 확인할 수 있다. 또, i = 4이면 (1, 2, 3, 4), (2, 3, 4, 5) ... 등 마찬가지로 N이 홀수이고 (N % i ) == ( i / 2) 가 성립한다.

 i가 홀수냐 , 짝수냐에 따라 상황이 맞아떨어지는지 확인하고 시작 수를 잡고, 시작 수가 음수라면 pass 아니면 출력해주면 된다.

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, L, T = -1;
	bool check = false;
	cin >> N >> L;
	int temp = (L * (L - 1)) / 2;
	for (int i = L; i <= 100; i++) {
		if (i % 2 == 1 && N % i == 0) {
			T = (N / i) -(i / 2);
		}
		else if(i % 2 == 0 && N % i == 1){
			T = N / i - (i / 2) + 1;
		}
		if (T >= 0) {
			for (int j = 0; j < i; j++)
				cout << T + j << ' ';
			check = true;
			break;
		}
	}
	if (!check)
		cout << -1;
	return 0;
}

---