[백준] JavaScript - 파도반 수열 (9461)

개요

문제 이름: 파도반 수열 (9461)
문제 링크: https://www.acmicpc.net/problem/9461
플랫폼: 백준
알고리즘 분류: 다이나믹 프로그래밍
소요 시간: 50분

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 다이나믹 프로그래밍이라고 불리는 동적 계획법을 사용하여 파도반 수열의 N번째 값을 구하는 문제입니다.

 

파도반 수열은 다음과 같은 점화식을 가집니다.

• P(N) = P(N-2) + P(N-3)
• N >= 4

이는 N번째 파도반 수의 길이는 N-2번째 파도반 수의 길이와 N-3번째 파도반 수의 길이의 합과 같다는 것을 의미합니다.

이 점화식을 활용하면 N번째 파도반 수의 길이를 계산할 수 있습니다.

 

동적 계획법의 핵심은 이전에 계산한 결과를 저장해 두고 필요할 때 그 값을 사용하는 것입니다. 이를 통해 중복 계산을 피할 수 있습니다. 이 문제에서는 배열 dp를 사용하여 이전에 계산한 파도반 수열의 값을 저장합니다. dp[i]는 i번째 파도반 수의 길이를 나타냅니다.

 

주어진 점화식을 사용하여 dp 배열을 채워나가면서 N번째 파도반 수의 길이를 계산할 수 있습니다.

• P(1), P(2), P(3)은 모두 1로 주어집니다.
• P(4)부터는 점화식 P(N) = P(N-2) + P(N-3)을 사용하여 계산합니다.

예를 들어, P(4)를 계산하려면 P(2)와 P(1)의 값을 더하면 됩니다.

• P(4) = P(2) + P(1) = 1 + 1 = 2

마찬가지로 P(5)는 P(3)과 P(2)의 합, P(6)은 P(4)와 P(3)의 합으로 계산할 수 있습니다. 따라서 dp 배열을 사용하여 이전에 계산한 값을 저장하면서 N번째 파도반 수의 길이를 효율적으로 계산할 수 있습니다.

 

이 문제의 요구사항은 다음과 같습니다.

1. 첫째 줄에 테스트 케이스의 개수 T가 주어집니다. (1 <= T <= 100)
2. 각 테스트 케이스는 한 줄로 이루어져 있으며, N이 주어집니다. (1 <= N <= 100)
3. 각 테스트 케이스마다 P(N)을 출력해야 합니다.

이를 바탕으로 문제 풀이 방식을 요약하면 다음과 같습니다.

1. 테스트 케이스의 개수 T를 입력받습니다.
2. T개의 테스트 케이스에 대해 각각 다음을 수행합니다.
   1. N을 입력받습니다.
   2. 크기가 N+1인 dp 배열을 생성하고 모든 값을 0으로 초기화합니다.
   3. 초기값 1이 들어간 P(1), P(2), P(3)을 dp 배열에 저장합니다.
   4. 4부터 N까지 반복하면서 점화식 P(N) = P(N-2) + P(N-3)을 사용하여 dp 배열을 채웁니다.
3. dp[N]을 출력합니다. 이는 N번째 파도반 수의 길이입니다.

 

시도

1차 시도  (성공)

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

// 첫 번째 줄의 테스트 케이스 개수
const T = parseInt(input[0]);

// 파도반 수열의 N번째 값을 구하는 함수
function solution(N) {
	// dp 배열 초기화 (0부터 N까지의 크기)
	const dp = new Array(N + 1).fill(0);

	// 기본 값 설정
	dp[1] = 1; // P(1) = 1
	dp[2] = 1; // P(2) = 1
	dp[3] = 1; // P(3) = 1

	// 4부터 N까지 파도반 수열 값 계산
	for (let i = 4; i <= N; i++) {
		// P(N) = P(N-2) + P(N-3)
		dp[i] = dp[i - 2] + dp[i - 3];
	}

	// N번째 값 반환
	return dp[N];
}

for (let i = 1; i <= T; i++) {
	// input[i]에서 N값을 가져와 정수로 변환
	const N = parseInt(input[i]);
	// 결과 출력
	console.log(solution(N));
}

이 코드는 DP를 사용하여 파도반 수열의 N번째 값을 계산합니다.

 

1. 입력 처리
   1. fs 모듈을 사용하여 표준 입력에서 데이터를 읽어옵니다.
   2. 입력을 읽어와 줄 단위로 분리합니다.
   3. 첫 번째 줄에서 테스트 케이스의 개수 T를 파싱(추출-가공)합니다.
2. 파도반 수열 계산 함수 (solution)
   1. solution 함수는 N을 매개변수로 받아 파도반 수열의 N번째 값을 계산합니다.
   2. dp 배열을 크기 N+1로 초기화하고 모든 값을 0으로 설정합니다.
   3. 기본 값인 P(1), P(2), P(3)을 미리 설정합니다.
   4. 반복문을 사용하여 4부터 N까지의 파도반 수열 값을 계산합니다.
   5. 점화식 P(N) = P(N-2) + P(N-3)을 사용하여 이전에 계산한 값을 활용합니다.
   6. 최종적으로 N번째 파도반 수열 값인 dp[N]을 반환합니다.
3. 테스트 케이스 처리
   1. 반복문을 사용하여 각 테스트 케이스를 처리합니다.
   2. input[i]에서 N 값을 가져와 정수로 변환합니다.
   3. solution 함수를 호출하여 해당 N에 대한 파도반 수열 값을 계산합니다.
   4. 계산 결과를 출력합니다.

 

마지막으로 테스트 케이스의 개수 T만큼 반복하면서 각 테스트 케이스에 대해 N값을 입력받고 solution 함수를 호출하여 결과를 출력합니다.

 

사용된 주요 메서드

• fill(): 배열의 시작 인덱스부터 끝 인덱스의 이전까지 정적인 값 하나로 채웁니다.
• parseInt(): 문자열 인자를 파싱하여 특정 진수(수의 진법 체계에 기준이 되는 값)의 정수를 반환합니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(T * N)
  • 테스트 케이스의 개수 T만큼 반복하면서, 각 테스트 케이스마다 solution 함수를 호출합니다.
  • solution 함수 내부에서는 N까지 반복하면서 파도반 수열 값을 계산하므로 O(N)의 시간이 소요됩니다.
  • 따라서 전체 시간 복잡도는 O(T * N)입니다.
• 공간 복잡도: O(N)
  • solution 함수 내부에서 동적 계획법을 위한 dp 배열을 생성하고 사용합니다.
  • dp 배열은 N+1 크기로 생성되므로 O(N)의 공간을 차지합니다.
  • 그 외에는 추가적인 공간을 사용하지 않으므로, 전체 공간 복잡도는 O(N)입니다.