문제 설명
N x 2의 공간에 2 x 1 크기의 타일을 채우는 방법의 수를 구하는 문제입니다.
주어진 공간의 크기가 N일 때, 여러 가지 방법으로 타일을 이어 붙여서 공간을 가득 채우는
경우의 수를 계산하는 것이 목표입니다.
이 문제는 동적 프로그래밍(Dynamic Programming) 기법을 활용해 해결할 수 있습니다.
각 타일의 배치 방식에 따라 이전의 상태를 이용해 현재 상태를 계산하는 방식으로 접근하게 됩니다.
문제 예제
예를 들어, N이 3일 경우 다음과 같은 배치 방법이 존재합니다:
- 타일을 세로로 3개 배치
- 타일을 가로로 2개, 세로로 1개 배치
- 타일을 세로로 1개, 가로로 2개, 세로로 1개 배치
- 타일을 가로로 1개, 세로로 2개, 가로로 1개 배치
위와 같은 배치를 통해 출력 결과는 5가 됩니다.
문제 풀이 과정
1단계: 상태 정의
문제를 해결하기 위해 우선적으로 상태를 정의해야 합니다.
f(N)이라는 함수가 N x 2 공간을 채우는 경우의 수라고 할 때,
다음과 같은 점화식을 세울 수 있습니다:
f(N) = f(N-1) + f(N-2)
여기서 f(N-1)은 N-1 x 2 공간에 타일을 세로로 놓은 경우이며,
f(N-2)는 N-2 x 2 공간에 타일을 두 개 가로로 놓은 경우를 의미합니다.
2단계: 초기 조건 정의
초기 조건을 정해야 합니다. N이 1일 때는 타일을 세로로 하나 배치할 수 있으므로 f(1) = 1입니다.
N이 2일 때는 타일을 두 개 세로 또는 가로로 놓을 수 있으므로 f(2) = 2입니다.
3단계: 점화식을 이용한 해결 방법
점화식을 이용해 N까지 차례로 계산해 나갈 수 있습니다.
배열을 사용할 수도 있지만, 두 개의 변수만으로도 충분히 가능합니다.
이전 두 값만 알면 다음 값을 계산할 수 있기 때문입니다.
자바 코드 예시
public class Tiling {
public static void main(String[] args) {
int N = 5; // 예를 들어 N을 5로 설정
System.out.println("2 x " + N + " 공간을 채우는 경우의 수: " + countWays(N));
}
static int countWays(int N) {
if (N == 1) return 1; // 기본 조건 1
if (N == 2) return 2; // 기본 조건 2
int[] dp = new int[N + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 점화식
}
return dp[N];
}
}
시간 복잡도와 공간 복잡도 분석
위 예제에서 시간 복잡도는 O(N)으로, N에 비례하여 증가합니다. 이는 모든 상태를 한 번씩 계산하기 때문입니다.
공간 복잡도는 O(N)이며, dp 배열을 사용하여 저장하기 위해 필요합니다.
그러나 변수를 두 개만 사용해도 가능하므로 O(1)로 최적화할 수 있습니다.
결론
2*N 타일 채우기 문제는 동적 프로그래밍의 대표적인 예제로,
메모리 사용을 최적화하면서 효율적인 알고리즘을 구현하는데 큰 도움이 됩니다.
이러한 문제를 통해 기본적인 알고리즘과 데이터 구조에 대한 이해를 심화할 수 있으며,
다양한 변형 문제로 연습할 수 있습니다. 시작해보세요!