[C++] 백준 1024번 수열의 합

1. 문제이해

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

1024번: 수열의 합

 

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 정수 리스트를 구하는 것이 목표이다.

단, 정수 리스트는 음수가 아니어야 하며, 연속된 숫자들이어야 한다.

 

 

 

2. 문제풀이

 

간단한 문제인것 같지만, 조금 까다로운 문제이다.

처음에는 그저 무조건 길이가 L인 리스트를 구하는 것이라고만 생각하고 문제를 풀었는데,

실은 길이가 L이상인 리스트들 중 가장 짧은 정수 리스트를 구하는 문제였다.

즉, 문제에서 구해야 하는 리스트를 다시 한 번 정의하자면,

합이 N이고, 길이가 L이상, 음수가 아닌 가장 짧은 연속된 정수들을 구하는 것이 목표이다.

 

그렇다면, 위와 같은 리스트를 구하는 방법을 알아보자.

정수들은 모두 연속된 정수들이기 때문에, 첫 번째 정수가 a, 길이가 L인 리스트의 합(N)은 다음과 같다.

 

리스트의 길이 (L)	리스트의 구성 (단, 첫번째 값은 a라 가정)	리스트의 합 (N)
1	a	a
2	a, a+1	2a + 1
3	a, a+1, a+2	3a + 3
4	a, a+1, a+2, a+3	4a + 6
5	a, a+1, a+2, a+3, a+4	5a + 10
6	a, a+1, a+2, a+3, a+4, a+5	6a + 15
L	a, a+1, a+2, ..., a+(L-1)	La + 1 + 2 + ... + (L-1)

 

위 표와 같이, 리스트의 길이 L에 따라 리스트의 합은 다음과 같은 식을 띄게 된다.

따라서, 위 표에서 도출한 식을 통해 첫번째 정수 값인 a로 정리하면, 다음과 같은 식을 얻을 수 있다.

a = (N -  constant) / L

(여기서 constant는 리스트의 합 부분에서 상수항의 합을 의미한다.

상수항의 합은 1부터 (L-1) 까지의 합을 뜻한다.

예를 들어, L = 2 일때 1, L = 3 일때 3,  L = 4 일때 6...)

 

따라서, 위와 같은 식을 이용해, 구하고자 하는 리스트의 첫번째 값을 구하고,

1. 위 식을 이용해 첫번째 값이 음이 아닌 정수인지를 확인,

2 - 1. 맞다면 해당 값을 기준으로 리스트를 출력하고,

2- 2. 아니라면, 리스트의 길이값(L)을 증가시킨 후 다음 과정을 반복해주면 된다. (단, L은 2이상 100이하의 정수)

 

 

 

3. 소스코드

#include <iostream>
#include <cctype>
using namespace std;

int main() {
	long double N, L;
	cin >> N >> L;

RE:	// 여기서부터 해당하는 수열을 찾을 때까지 루프 반복
	
	// 루프를 돌때마다 해당 값 초기화
	long double constant = 0;     // 상수
	long double first_num = 0;	  // 첫 번째 값

	for (int i = 1; i < L; i++) {
		constant += i;
	}
	first_num = (N - constant) / L;
	
	// 첫번째 값이 양의 정수 또는 0 이면 조건을 만족하는 수열
	if (int(first_num) == first_num && first_num >= 0) {
		for (int i = 0; i < L; i++) {
			cout << int(first_num) + i << " ";
		}
	}
	// 조건을 만족하는 수열이 아니라면
	else {
		// L이 100이 될때까지 만족하는 수열이 없다면, -1 출력
		if (L == 100) {
			cout << "-1";
		}
		// L이 100이 되지 않았다면, L값을 증가시킨 후 루프반복
		else {
			L++;
			goto RE;
		}
	}

	return 0;
}

리스트의 합인 N의 범위가 1,000,000,000보다 작거나 같은 자연수이기 때문에

모든 변수는 long double 형을 사용했다.

리스트의 합과 길이인 N과 L을 각각 입력받은 뒤, 루프를 시작한다. (RE : ) 필자는 goto문을 이용했다.

 

루프를 돌때마다 초기화해야되는 값인 상수의 합(constant),

리스트의 첫번째 정수(first_num)값을 0으로 초기화 해준다.

이후 for문을 통해 길이가 L일때의 상수의 합(constant)을 구해주고,

2. 문제풀이에서 도출한 식  a = (N -  constant) / L 을 통해 리스트의 첫번째 값(first_num)을 구해준다.

 

리스트의 첫 번째 값이 음수가 아닌 정수일 때만 모든 조건을 만족하므로,

if문을 통해 음수가 아닌 정수인지를 확인, 맞다면 해당 리스트를 출력한다.

 

만약 조건을 만족하는 수열이 아니라면, (첫번째 값이 음수이거나 정수가 아닌 경우)

L값이 100인지 확인 (L값의 범위는 2~100까지이므로),

100이라면 조건을 모두 만족시키는 리스트가 없는 것이므로 -1을 출력한다.

만약, L값이 100이 아니라면, L값을 증가시킨 후에 goto문을 통해 위의 과정을 반복한다.

 

 

---

무조건 길이가 L인 리스트만 취급하는 줄 알고 풀었다가 시간을 뺏긴 문제였다..

문제좀 잘 읽어야하는데 왜 한번에 이해가 되지 않는 걸까..😥

계속 노력해서 고칠 수 있도록 노력해야지..💪