1. 문제 설명
문제 설명
가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다
- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우
예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 가로의 길이 n은 5,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
입출력 예
n | result |
---|---|
4 | 11 |
입출력 예 설명
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
2. 문제 풀이
keyword
: stack-up 하는 DP, 모듈러 분배 법칙
안 풀려서 다른 사람의 풀이를 봤다. 그 중에서도 이해가 제일 잘가는 풀이로 설명 하겠다.
(1) 사전 지식
먼저 사용 되는 타일이 1 x 2 짜리 타일이므로, 홀수 칸의 바닥은 무조건 채우지 못한다.
따라서, DP의 stackup 되는 규칙성을 구하기 위해서는, 짝수 칸으로만 생각 해야한다. 그럼 n= 2부터 n = 8 까지 같이 알아보고 규칙성을 찾아보자.
ⓐ n=2 일 때,
n=2인 바닥을 전부 채우는 경우는 위의 3가지이다.
ⓑ n=4 일 때,
자, 이제부터 집중해야 한다.
n=4인 바닥을 타일로 채울 때는 다음 2가지의 유형이 존재한다.
첫 번째로, 이전 것들을 조합해 채우는 경우이다.
n=2인 타일에서 2칸 더 추가해서 이어나간다고 가정하자. 이때 저 추가된 물음표에 무엇이 들어갈까?
당연하게도, n=2에서 나왔던 3가지 경우의 수이다. 그렇다면 각 경우마다 3가지 버전이 더 생기므로, 3 x 3 = 9가지 경우가 나온다.
두 번째로, 이전 것들을 조합하지 않는 완전히 새로운 경우이다.
원래는 이전 경우의 수인 n=2 타일을 조합해서 만들었다면, 이번에는 그 각자의 영역을 침범하여 n=4 를 채우는 경우다. 이건 그냥 생각해내는 수 밖에 없다. 위와 같이 2가지 경우가 생겨난다.
ⓒ n=6 일 때,
이것도 n=4와 똑같이 2가지 유형으로 나누어서 생각해야한다.
첫 번째, 이전에 계산한 것들 조합
- n=4가 앞에 나오는 경우를 생각해보자. n=4인 타일을 가득 채우는 경우의 수마다, 나머지 n=2인 타일을 채우는 3가지 루트가 존재한다. 따라서 f(4)*f(2)가 된다.
- n=2가 앞에 오는 경우도 생각해야한다.
n=4를 채우는 경우의 수 중에 n=2인 경우 2가지를 조합해서 만든 것이 포함되어 있는데 왜 또 생각해야하죠?
라고 의문이 들 수 있겠다. 그 이유는, n=4의 2번째 유형인조합 하지 않고 타일을 전체 채우는 경우의 수
때문이다. n=2 타일링 + n=4의 (2)는 새로운 경우의 수라고 할 수 있겠다.
※주의점※
n=4의 두 번째 유형도 n=4 타일링 + n=2 타일링 조합에 포함된다! 다만 n=4의 두 번째 유형 + n=2 타일링과 n=2타일링 + n=4의 두번째 유형은 순서가 달라서 서로 다른 경우의 수로 체크되기 때문에 다시 세어준 것이다.
두 번째, 이전 것들을 조합하지 않는 완전히 새로운 경우
여기서도 2개다.
ⓓ n=8일 때,
첫 번째, 이전까지 나온 경우의 수들을 조합하는 경우
더 설명하지 않아도 될 것 같다.
- n=6 타일링 x n=2 타일링으로 만드는 조합 (이전 타일링 경우의 수 x n=2의 타일링 경우의 수)
- n=4, n=6 에서 나온 새로운 경우들을 이용한 조합 -> 이것은 지금까지 계속 2개씩만 나온 것으로 미루어 보아, 앞으로도 그럴 것이다. (가로가 n인 바닥의 타일링 x 2)
두 번째, 완전히 새로운 경우의 수
항상 2가지
점화식 계산
지금까지 알아본 규칙성으로 가로가 n인 바닥을 완전히 메우는 경우의 수는 다음과 같은 식으로 구할 수 있다.
3. 코드 분석
class Solution {
public long solution(int n) {
long [] dp = new long [n+1];
// 초기 값 설정
dp[2] = 3;
for(int i = 4; i <= n; i+=2){
// 초기 값 설정 (이전 꺼 * dp[2] 인 경우의 수 + 영역 범람하여 만들 수 있는 경우의 수 2개)
dp[i] = dp[i-2]*dp[2] + 2;
// dp 값 완성
for(int j = 2; j <= i-4; j+=2) {
dp[i] += dp[j]*2;
}
dp[i] = dp[i]%1000000007;
}
return dp[n];
}
}
모듈러 분배법칙은 잘 몰라서 사용하지 못했다. 이것도 이론 공부 해야겠다.
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[프로그래머스] 12981 영어 끝말잇기 (0) | 2024.06.17 |
---|---|
[프로그래머스] 12946 하노이탑 java 풀이 (0) | 2024.06.17 |
[Programmers] 12977 소수 만들기 Java (0) | 2024.06.16 |
[코드 트리] 배열 회전 2 Java (0) | 2024.06.14 |
💚 백준 1940 주몽 (0) | 2024.05.06 |