수 묶기

문제

백준 1744번 - 수 묶기

언어

JavaScript

순서도

주어진 수열에서 음수, 0, 1, 양수 끼리 별도로 분리하기
음수와 양수는 오름차순으로 정렬하기
각각 음수와 양수에서 수 묶기 연산 수행
총합 구하기

문제 풀이 step 1

길이가 N 인 수열이 주어졌을 때, 그 수열의 합을 구하려고 합니다.
하지만 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 합니다.
어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있습니다. 하지만 자기 자신을 묶는 것은 불가능합니다.
그리고 어떤 수를 묶게되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더합니다.
수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야 합니다.
수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합의 최댓값을 구하는 문제입니다.

문제 풀이 step 2

본 문제를 풀기 위해서는 바로 로직을 구현하기 보다는 수 묶기의 성질을 파악하는 것이 더 중요한 것 같습니다.
제가 파악한 성질은
1. 양수는 큰 수끼리 곱하는 것이 합을 최대로 만들고, 음수는 작은 수끼리 곱하는 것이 합을 최대로 만듭니다.
2. 0 은 양수랑은 더하는 것이 합을 최대로 만들고, 음수랑은 곱하는 것이 합을 최대로 만듭니다.
3. 양수랑 음수는 서로 곱하면 오히려 합을 작아지게 만듭니다.
4. 양수 중에서 1 은 곱하면 오히려 합을 작아지게 만들고, 대신 더하면 합을 최대로 만듭니다.
위와 같은 성질을 파악하고 나서 로직을 작성하니 쉽게 해결책을 찾을 수 있었습니다.

문제 풀이 step 3

우선, 수열에서 음수, 0, 1, 양수끼리 별도로 분리합니다. 그리고 음수와 양수 모두 오름차순으로 정렬합니다.
그리고 음수부터 처리합니다.
- 음수는 수 묶기를 하면 양수가 되니까 최대한 묶을 수 있는 만큼 묶는 것이 좋습니다.
- 단, 음수의 총 개수가 홀수라면 다 묶어도 결국 하나가 남게 될 것입니다. 그렇다면 그 남은 음수 한 개는 0 과 곱하는 것이 최선일 것입니다.
- 따라서 음수의 총 개수가 짝수면 모두 수 묶기를 하고, 홀수면 가장 큰 음수 하나만 0 과 곱하고 나머지를 수 묶기 하면 되겠습니다.
- 만약 0 이 하나도 없다면 그냥 더하는 수 밖에 없습니다.
0 은 처리할 것은 없고, 1 은 수 묶기를 할 경우 오히려 작아지므로 그냥 다 더하면 되겠습니다.
마지막으로 양수를 처리합니다.
- 양수의 총 개수가 짝수면 그냥 전부 수 묶기를 해주면 되고, 양수의 총 개수가 홀수면 가장 작은 양수만 더하고 나머지를 수 묶기 해주면 되겠습니다.
위 과정을 통해서 구한 총합을 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

const solution = (input) => {
	const minus = [];
	const zero = [];
	const one = [];
	const plus = [];

	// 음수, 0, 1, 양수 별도로 분리하기
	const n = Number(input[0]);
	for (let i = 1; i < n + 1; i++) {
		const num = Number(input[i]);

		if (num < 0) minus.push(num);
		else if (num === 0) zero.push(num);
		else if (num === 1) one.push(num);
		else plus.push(num);
	}

	// 오름 차순 정렬
	minus.sort((a, b) => a - b);
	plus.sort((a, b) => a - b);

	let sum = 0;

	// 가장 큰 음수 처리
	if (minus.length % 2 === 1) {
		const withZero = minus.pop();
		if (zero.length === 0) sum += withZero;
	}

	// 음수 게산 (가장 작은 음수 2 개씩 수 묶기)
	for (let i = 0; i < minus.length; i += 2) {
		sum += minus[i] * minus[i + 1];
	}

	// 가장 작은 양수 처리
	if (plus.length % 2 === 1) {
		sum += plus.shift();
	}

	// 양수 계산 (가장 큰 양수 2 개씩 수 묶기)
	for (let i = plus.length - 1; i >= 0; i -= 2) {
		sum += plus[i] * plus[i - 1];
	}

	// 1 계산
	sum += one.length;

	return sum;
};

console.log(solution(input));