[바미] 녹색거탑

문제

https://www.acmicpc.net/problem/24723

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();

const N = parseInt(input, 10);

// 내려오는 경우의 수를 계산하는 함수
function calculatePaths(N) {
    if (N === 1) {
        return 2;
    }
    return 2 ** N;
}

const result = calculatePaths(N);
console.log(result);

문제 해설

녹색거탑을 내려오는 경우의 수를 계산하는 문제입니다. 

 

녹색거탑은 N층이며, 각 층에서 인접한 아래층의 블록으로만 내려올 수 있기 때문에 탑의 높이 N이 주어질 때, 정상에서 바닥까지 내려오는 모든 경로의 수를 계산해야 합니다.

 

탑의 높이 N이 최대 5이기 때문에 모든 경우의 수를 직접 계산해도 성능에 문제가 없습니다. 그렇기 때문에 재귀적으로 접근하여 문제를 해결하였습니다.

 

각 층에서 내려오는 경우의 수는 다음과 같이 계산됩니다.

• 1층: 2개의 경로 (왼쪽 또는 오른쪽)
• 2층: 4개의 경로 (각 블록에서 두 블록으로 내려가는 방식이 2가지이므로 2층의 모든 블록에 대해 2 * 2)
• N층: 각 층의 블록 수는 층수와 동일하고, 각 블록마다 내려갈 수 있는 경로의 수는 2가지이므로 총 경로 수는 
  2^𝑁이 됩니다.

이를 바탕으로 녹색거탑의 높이 N이 주어졌을 때 내려오는 경로의 수를 계산하는 코드를 위와 같이 작성하였습니다.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

calculatePaths(N) 함수는 단순히 지수 연산을 수행하기 때문에 시간복잡도는 O(1)이 됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

이 코드의 공간 복잡도를 살펴보면

• N은 입력을 저장하는 정수 변수기 때문에 공간 복잡도는 O(1)이 됩니다.
• result는 계산된 결과를 저장하는 정수 변수기 때문에 공간 복잡도는 O(1)이 됩니다.
• 함수 호출 스택의 깊이는 최대 O(1)입니다.

따라서 전체 코드의 공간 복잡도는 O(1)이 됩니다.