[Baekjoon/C++] 1024번 - 수열의 합

Baekjoon Online Judge

문제로 이동

 

문제

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

 

입력

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

 

출력

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

 

---

예제 입력	예제 출력
18 2	5 6 7
18 4	3 4 5 6
18 5	-1
45 10	0 1 2 3 4 5 6 7 8 9
1000000000 2	199999998 199999999 200000000 200000001 200000002

---

풀이

#include <iostream>
using namespace std;

int main() {
	int N, L; // 합 N, 길이 L
	cin >> N >> L;

	int num = 0;
	for (int i = 0; i < L; i++)
		num += i;

	// 입력된 L보다 긴 수열이 필요할 때
	if ((N - num) % L != 0 || (N - num) / L < 0) {
		for (int i = 0; ; i++) {
			num += L;
			L++;

			// 수열이 없을 때
			if (L > 100) {
				L = -1;
				break;
			}

			// 수열을 찾았을 때
			if ((N - num) % L == 0 && (N - num) / L >= 0)
				break;
		}
	}

	// 출력
	if (L == -1)
		printf("-1");
	else
		for (int i = 0; i < L; i++)
			printf("%d ", ((N - num) / L) + i);
	printf("\n");

	return 0;
}

 

18 = n + (n + 1) = 2n + 1				2n = 17 (나누어 떨어지지 않음)
18 = n + (n + 1) + (n + 2) = 3n + 3			3n = 15 (나누어 떨어짐)
18 = n + (n + 1) + (n + 2) + (n + 3) = 4n + 6		4n = 12 (나누어 떨어짐)
18 = 5n + 10     					5n = 8 (나누어 떨어지지 않음)

(N - (0부터 L-1까지의 합)) % L == 0을 만족하는 L을 찾는 방식으로 수열을 찾았다.

 

	int num = 0;
	for (int i = 0; i < L; i++)
		num += i;

먼저 입력된 최소 수열의 길이 L - 1까지의 숫자의 합 num을 구했다.

 

	// 입력된 L보다 긴 수열이 필요할 때
	if ((N - num) % L != 0 || (N - num) / L < 0) {
		for (int i = 0; ; i++) {
			num += L;
			L++;

			// 수열이 없을 때
			if (L > 100) {
				L = -1;
				break;
			}

			// 수열을 찾았을 때
			if ((N - num) % L == 0 && (N - num) / L >= 0)
				break;
		}
	}

(N - num) % L이 0아니고, (N - num) / L가 음수라면 위의 코드가 실행되게끔 했다.

 - 이 부분에서 (N - num) / L < 0을 빼먹어서 고생을 했다. 이 부분이 빠져도 예제로 나온 수들은 모두 돌아가기 때문이다.   - 이 부분이 빠졌을 때의 반례는 2 4처럼 (N - num) % L != 0에 걸리지 않으면서 (N - num) / L < 0가 되는 수이다.

    (게시판 질문을 통해 찾은 반례)

 

위 코드는 수열의 길이를 1씩 증가시켜보면서 가장 짧은 연속된 음이 아닌 정수 수열을 찾는다. 만약 그 길이가 100을 넘으면 L의 값을 -1로 바꾸고 수열을 찾지 못했음을 표시한다.

 

	// 출력
	if (L == -1)
		printf("-1");
	else
		for (int i = 0; i < L; i++)
			printf("%d ", ((N - num) / L) + i);
	printf("\n");

L이 -1이면 수열을 찾지 못한 것이기에 -1을 출력한다.

수열을 찾은 경우 (N - num) / L에 0부터 L - 1까지의 수를 더한 값을 하나하나 출력하도록 했다.