수열의 합

문제

백준 1024번 - 수열의 합

언어

JavaScript

순서도

공식 만들기
2 ~ 100 까지 공식에 적용해보면서 가능한 경우 찾기
가능한 경우가 있다면 그 경우를 출력하고, 없다면 -1 출력하기

문제 풀이 step 1

N 과 L 이 주어질 때, 합이 N 이면서, 길이가 L 인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 문제입니다.
우선, 공식에 대한 설명부터 하겠습니다.
- 합이 N 이면서, 길이가 L 인 수열은 다음과 같이 표현할 수 있습니다.
- N = x + (x + 1) + (x + 2) + ... + (x + L - 1)
- N = L * x + (1 + 2 + ... L - 1)
- N = L * x + ((L - 1) * L) / 2
위의 공식에 주어진 N 과 L 을 적용시켰을 때, 등호가 성립하는 x 가 존재한다면 그 때의 수열을 출력하면 정답입니다.
문제에서 수열의 길이가 적어도 L 인 가장 짧은 연속된 음이 아닌 정수의 수열을 구하라고 했고, 길이가 100 보다 같거나 작아야 한다고 했으므로,
- 범위는 L ~ 100 이고,
- x 는 0 이상이여야 합니다.
추가 설명은 주석으로 작성하겠습니다.

후기

투 포인터 방식으로 적용했으나, 역시 범위가 커서인지 시간 초과가 발생해서 수학 공식으로 풀게 되었습니다.
수학적으로 접근해야겠다는 생각을 전혀 못해서, 공식을 제 스스로 도출해내진 못했습니다.
그래서 어떤 분의 블로그를 참고하게 되어서, 출처를 남겼습니다.
길이가 L 인 수열의 합의 공식은 x + (x + 1) + (x + 2) + ... + (x + L - 1) !!

Reference.

참고한 공식의 출처 블로그

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const [n, l] = input[0].split(" ").map(Number);

	// 범위는 l ~ 100
	for (let i = l; i <= 100; i++) {
		// 공식을 이용해서 x 구하기
		const x = parseInt((n - (i * (i - 1)) / 2) / i);

		// x 가 음이 아닌 정수라면,
		if (x >= 0 && i * x + (i * (i - 1)) / 2 === n) {
			const res = [];
			for (let j = 0; j < i; j++) {
				res.push(x + j);
			}

			// 수열 구해서 출력하기
			return res.join(" ");
		}
	}

	// 범위가 100 을 넘어가거나 그러한 수열이 없는 경우 -1 출력
	return -1;
};

console.log(solution(input));