부분수열의 합

문제

언어

  • JavaScript

순서도

  1. 수열 S 로 만들 수 있는 모든 부분 수열 만들고, 그 부분 수열의 합 구해보기
  2. 각 부분 수열의 합을 배열에 기록하기
  3. 배열을 순회하며, 부분 수열로 만들 수 없는 수 중에서 최솟값을 찾아서 출력

문제 풀이 step 1

  • 수열 S 가 주어졌을 때, 수열 S 의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 문제입니다.
  • 우선, 재귀 함수를 이용해서 만들 수 있는 모든 부분 수열의 합을 만들어봅니다.
  • 각각의 합을 배열에 저장하고, 그 배열을 처음부터 순회하며 부분 수열로 만들 수 없는 수 중에서 최솟값을 찾아서 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 알고리즘의 소요 시간을 줄이는 방법에는 참 여러가지 방법이 있는 것 같습니다.
  • 기존의 반복시마다 합을 구하는 방식을 통해서 나중에 합을 구하는 과정을 제외
    • rec(n, arr, sum + arr[depth], depth + 1, sumArr);
    • 저는 배열에 다 저장한 다음에 마지막에 합을 구하는 방식을 사용했었습니다.
  • 어떠한 값을 배열의 index 로 사용하는 방식을 통해서 불필요한 연산 삭제
    • if (sum > 0) sumArr[sum] = true;

소스 코드 1

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

// 모든 부분 수열의 합을 만들어보는 재귀함수
const rec = (n, arr, sum, depth, sumArr) => {
	if (depth === n) {
		// index 형태로 어떠한 배열에 저장
		if (sum > 0) sumArr[sum] = true;
		return;
	}

	if (depth > n) return;

	rec(n, arr, sum + arr[depth], depth + 1, sumArr);
	rec(n, arr, sum, depth + 1, sumArr);
};

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input[1].split(" ").map(Number);
	const max = arr.reduce((ac, v) => ac + v);

	const sumArr = [true];
	rec(n, arr, 0, 0, sumArr);

	// 배열을 처음부터 순회하며 부분 수열로 만들 수 없는 최솟값 찾아서 출력
	let num = 0;
	for (; num <= max + 1; num++) {
		if (sumArr[num] !== true) break;
	}

	return num;
};

console.log(solution(input));