BOJ (C/C++) 1024번: 수열의 합

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

1024번: 수열의 합

---

풀이

L개의 정수를 더해 N이 되어야 하므로 그 수들은 N/L 부근에 있다. 따라서 mid=N/L로 두고 L이 짝수/홀수일 때 리스트가 달라지므로 그 경우로 나눴다. 이 때 시작 지점(s)과 끝 지점(e)을 구해 에러 조건 판별( -1 출력)과 출력에 사용했다.
(에러 검증은 반복문 안에서 수행해야 시간초과가 나지 않는다)또한 L이 짝수일 경우 3 4 5 6 7 8 처럼 가운데 두 수의 합과 mid-n, (mid+1)+n의 합은 동일하고,
홀수일 경우 1 2 3 4 5 처럼 가운데 수의 2배가 mid-1, mid+1의 합과 동일하므로 이를 이용해 수열의 합을 구했다.
(반복문으로 실행 시 시간초과)

 

또한 5 6 7, 6 7 8 처럼 한 자리씩 차이나는 수를 sum_m, sum_M으로 정하여 N이 이 사이의 값일 경우 L을 증가시켜줬다.N이 작은 합보다 작으면 수열의 위치를 1씩 증가, N이 큰 합보다 크면 수열의 위치를 1씩 감소시켜 N에 가까워지게 함.

---

코드

#include <stdio.h>
int main() {
	int N, L;
	int mid, s, e, sum_m, sum_M;
	bool change = true;

	scanf("%d %d", &N, &L);
	while (1) {

		// L 변화 있을 때만
		if (change) {
			mid = N / L;
			if (L % 2) s = mid - L / 2, e = mid + L / 2;
			else s = mid - L / 2 + 1, e = mid + L / 2;

			if (L % 2) sum_m = mid + (2 * mid)*(L / 2);
			else sum_m = (2 * mid + 1)*(L / 2);

			sum_M = sum_m - s + (e + 1);

			change = false;
		}

		//error
		if (s < 0 || e - s + 1>100) {
			printf("-1");
			return 0;
		}

		if (sum_m == N) break;
		else if (sum_M == N) {
			s++, e++;
			break;
		}

		if (sum_m < N&&N < sum_M) L++, change = true;
		else if (N < sum_m) sum_M = sum_m, sum_m = sum_m - e + (s - 1);
		else if (N > sum_M) sum_m = sum_M, sum_M = sum_M + (e + 2) - (s + 1);
	}
	//print
	for (int i = s; i <= e; i++) printf("%d ", i);

	return 0;
}