[백준] JavaScript - 1, 2, 3 더하기 (9095)

개요

문제 이름: 1, 2, 3 더하기 (9095)
문제 링크: https://www.acmicpc.net/problem/9095
플랫폼: 백준
알고리즘 분류: 다이나믹 프로그래밍
소요 시간: 10분

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있습니다. 동적 계획법은 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 재활용함으로써 효율적으로 문제를 해결하는 알고리즘입니다.

 

이 문제에서는 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구해야 합니다. 이를 위해 우선 작은 숫자부터 시작하여 점진적으로 큰 숫자에 대한 해답을 구하는 접근 방식을 취합니다.

• 1을 만드는 방법: 1 (1가지)
• 2를 만드는 방법: 1+1, 2 (2가지)
• 3을 만드는 방법: 1+1+1, 1+2, 2+1, 3 (4가지)

1, 2, 3에 대한 경우의 수는 위와 같습니다.

• 3을 만드는 방법에 1을 더하는 경우
• 2를 만드는 방법에 2를 더하는 경우
• 1을 만드는 방법에 3을 더하는 경우

이를 바탕으로 4부터 n까지의 숫자에 대한 경우의 수를 구할 수 있습니다. 예를 들어, 4를 만드는 방법은 위처럼 구할 수 있습니다.

 

이를 일반화하면, i를 만드는 방법의 수는 (i-1)을 만드는 방법의 수 + (i-2)를 만드는 방법의 수 + (i-3)을 만드는 방법의 수와 같습니다. 이를 점화식으로 표현하면 ' dp[i] = dp[i-1] + dp[i-2] + dp[i-3]'라고 할 수 있습니다.

 

따라서 이 문제는 1부터 n까지의 숫자에 대해 위의 점화식을 적용하여 각 숫자를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 것으로 요약할 수 있습니다.

1. 테스트 케이스의 개수 T를 입력받습니다.
2. 각 테스트 케이스에 대해 숫자 n을 입력받습니다.
3. 크기가 11인 dp 배열을 생성하고 모든 요소를 0으로 초기화합니다.
4. 기본 케이스인 dp[1], dp[2], dp[3]의 값을 각각 1, 2, 4로 초기화합니다.
5. 4부터 n까지의 숫자에 대해 점화식 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]을 적용하여 dp 배열을 채웁니다.
6. dp[n]의 값을 반환하여 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구합니다.
7. 각 테스트 케이스에 대한 결과를 result 문자열에 추가합니다.
8. 모든 테스트 케이스에 대한 결과를 한 번에 출력합니다.

코드에서는 위와 같은 접근 방식을 사용했습니다.

 

시도

1차 시도  (성공)

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

// 첫 번째 줄의 테스트 케이스 수를 숫자로 변환
const T = Number(input[0]);

// input 배열의 첫 번째 요소(T)를 제외한 나머지를 숫자 배열로 변환
// slice(1): 인덱스 1부터 끝까지 추출
// map(Number): 각 문자열을 숫자로 변환
const numbers = input.slice(1).map(Number);

// 주어진 숫자 n에 대한 해결 방법 수를 계산하는 함수
function solution(n) {
	// 크기 11의 배열 생성 (0부터 10까지의 인덱스)
	// fill(0): 모든 요소를 0으로 초기화
	const dp = new Array(11).fill(0);

	// 기본 케이스 초기화
	// 각각의 경우의 수를 직접 계산하여 저장
	dp[1] = 1; // 1
	dp[2] = 2; // 1+1, 2
	dp[3] = 4; // 1+1+1, 1+2, 2+1, 3

	// 4부터 n까지 각 숫자에 대한 방법의 수 계산
	for (let i = 4; i <= n; i++) {
		// 점화식 적용
		// i-1의 모든 경우에 1을 더하는 경우
		// i-2의 모든 경우에 2를 더하는 경우
		// i-3의 모든 경우에 3을 더하는 경우
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
	}

	// 계산된 결과 반환
	return dp[n];
}

// 모든 테스트 케이스의 결과를 저장할 문자열
let result = "";

// 각 테스트 케이스에 대해 순차적으로 처리
for (let i = 0; i < T; i++) {
	// solution 함수의 결과를 문자열에 추가
	// 각 결과 뒤에 줄바꿈 추가
	result += solution(numbers[i]) + "\n";
}

// 최종 결과 출력
// trim(): 마지막 줄바꿈 제거
console.log(result.trim());

1. fs 모듈을 사용하여 입력을 읽어옵니다. /dev/stdin은 표준 입력을 나타냅니다.
2. input 배열의 첫 번째 요소는 테스트 케이스의 개수 T이고, 나머지 요소는 각 테스트 케이스의 숫자 n입니다.
3. numbers 배열은 input 배열에서 첫 번째 요소를 제외한 나머지 요소를 숫자로 변환한 배열입니다.
4. solution 함수는 주어진 숫자 n에 대해 1, 2, 3의 합으로 나타내는 방법의 수를 계산합니다.
   1. dp 배열을 생성하고 크기를 11로 설정하며, 모든 요소를 0으로 초기화합니다.
   2. 기본 케이스인 dp[1], dp[2], dp[3]의 값을 각각 1, 2, 4로 초기화합니다.
   3. 4부터 n까지의 숫자에 대해 점화식 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]을 적용하여 dp 배열을 채웁니다.
   4. dp[n]의 값을 반환하여 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구합니다.
5. result 문자열에 각 테스트 케이스에 대한 결과를 추가합니다.
6. 모든 테스트 케이스에 대한 결과를 한 번에 출력합니다.

 

사용된 주요 메서드

• Array.prototype.slice: 배열의 일부분을 추출하여 새로운 배열을 반환하는 메서드입니다.
  • input.slice(1)은 input 배열의 인덱스 1부터 끝까지 추출하여 새로운 배열을 만듭니다.
• Array.prototype.map: 배열의 각 요소에 대해 주어진 콜백 함수를 호출하고, 그 결과로 새로운 배열을 생성하는 메서드입니다.
  • input.slice(1).map(Number)는 추출한 배열의 각 요소를 Number 함수를 사용하여 숫자로 변환한 새로운 배열을 만듭니다.
• Array.prototype.fill: 배열의 시작 인덱스부터 끝 인덱스까지 정적인 값 하나로 채우는 메서드입니다.
  • new Array(11).fill(0)은 크기가 11인 배열을 생성하고 모든 요소를 0으로 초기화합니다.
• String.prototype.trim: 문자열의 양 끝에서 공백 문자(스페이스, 탭, 개행 등)를 제거한 새로운 문자열을 반환하는 메서드입니다.
  • result.trim()은 result 문자열의 마지막에 추가된 개행 문자를 제거합니다.

 

시간 복잡도 및 공간 복잡도

• 시간복잡도: O(n * m)
  
  • 여기서 n는 테스트 케이스의 개수이고, m은 입력된 숫자의 최댓값입니다. 각 테스트 케이스마다 1부터 m까지의 숫자에 대해 점화식을 계산하므로 O(m)의 시간 복잡도를 가지며, 총 n개의 테스트 케이스가 있으므로 전체 시간복잡도는 O(n * m)입니다.
• 공간 복잡도: O(n)
  • 입력된 숫자의 최댓값에 해당하는 크기의 dp 배열을 사용하므로 O(n)의 공간 복잡도를 가집니다. 추가로 입력 배열과 결과 문자열을 저장하는 공간이 필요하지만, 이는 입력 크기에 비례하므로 전체 공간복잡도는 O(n)으로 볼 수 있습니다.