[프로그래머스✈][연습문제] 3 x N 타일링 풀이
👓 문제 요약
유명한 DP 문제 2 x N 타일링의 업그레이드 버전
이젠 세로의 길이가 2가 아니라 3이다!!
DP 공식을 잘 유도하면 쉽게 풀 수 있다!!
자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기
🔑 문제 풀이
dp 공식을 유도해야하는데 순서대로 잘 그려보면 알 수 있다.
일단 n이 홀수면 타일링을 할 수 없으므로 답은 0 이다.
그려보면
- n : 2 일 때 답은 3
- n : 3 일 때 답은 0
- n : 4 일 때 답은 11 이다.
- n : 6 일 때는 답이 41 이다. (너무 많이 그려야해서 찾아봤다)
- n : 8 일 때는 답이 153 이다. (너무 많이 그려야해서 찾아봤다)
n 이 4일 때를 생각해보자.
- 3X2 타일링 의 방법의 수 * 3X2 타일링의 방법의 수 = 9
- n 이 4일 때만 만들 수 있는 방법 2를 더하면 11가지의 경우가 있다.
(ㅣ = ㅣ 이런식으로 가운데 가로 타일을 놓는 것)
n 이 6일 때를 생각해보자.
- 3X4 타일링의 방법의 수 * 3X2 타일링의 방법의 수 = 33
(3X4 에는 3X2와 3X2로 만들 수 있는 모든 경우의 수가 포함되어 있다.)
- n 이 6일 때만 만들 수 있는 타일의 수 2
- 또 생각 해야할 것이 3 x 2 의 타일링의 방법의 수 * 2 와 3 X 4 만이 만들 수 있는 타일의 경우 2가지를 곱한 것을 더한다. = 6
왜냐하면 3X4 타일링의 방법의 수 * 3X2 타일링의 방법의 수를 할 때 오른쪽 4칸을 포함하는 오직 3X4만이 만들 수 있는 2가지 경우의 수는 들어가있지 않기 때문이다.
n 이 8 일 때는
- 위와 마찬가지로 3X6 일때 타일링의 방법의 수 * 3X2 일 때 타일링의 방법의 수 = 123
- n 이 8일 때만 만들 수 있는 경우 : 2
- 3X2 일 때 타일링의 방법의 수 * 3X6일 때만 만들 수 있는 타일링의 수 = 6
- 3X4 일 때 타일링의 방법의 수 * 3X4일 때만 만들 수 있는 타일링의 수 = 22
감이 오는가?? 3XN 을 타일링 할 때는
- 3X(n-2) * 3X2 를 곱한 값
- n 일 때만 만들 수 있는 2가지 경우
- 3X2 * (3X(n-2)일 때만 만들 수 있는 경우 2개)
- 3X4 * (3X(n-4)일 때만 만들 수 있는 경우 2개).... 앞의 수가 3X(n-2)에 해당할 때까지 해주면 된다.
다시 말하면
- N-2 일때 경우의 수 * 3(3X2타일링의 방법의 수)
- N일 때만 만들 수 있는 경우 2개
- N-2k(k = 1,2,3....) N-2k가 N-2 가 될 때까지의 수 각각에 2를 곱한 값을 더해주면 된다.
🥽 소스코드 및 소스해석
프로그래머스 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 테스트 코드가 존재합니다.
#include <string>
#include <vector>
using namespace std;
//풀이
//ex n = 8
//더해야할 것
//answer(6) * answer(2)
//answer(2) * 2 (n 이 6일때만 존재하는 2개의 경우)
//answer(4) * 2 (n 이 4일때만 존재하는 2개의 경우)
//dp1의 인덱스는0 부터 시작되며 n이 2씩 증가할 때 마다의 값이 저장됨 n이 2,4,6,8 ....일 때
//dp2는 인덱스 0 부터 인덱스 n - 2 까지의 각각의 값 *2 의 합이 저장.
long long dp1[4096];
long long dp2[4096];
int solution(int n);
int main() {
solution(16);
}
int solution(int n) {
if (n % 2 == 1)
return 0;
dp1[0] = 3;
dp1[1] = 11;
dp2[1] = 6;
for (int i = 2; i < n / 2; i++) {
dp1[i] = (dp1[i - 1] * 3 + dp2[i - 1] + 2) % 1000000007;
dp2[i] = (dp1[i - 1] * 2 + dp2[i - 1]) % 1000000007;
}
return dp1[n / 2 - 1];
}
🔨 문제 후기
디피는 어렵다. 단순한 문제 일 수록 더욱 어렵다.
생각을 많이하고 시간을 많이 소요하는 문제들도 생각보다 많다.
화이팅!
Author And Source
이 문제에 관하여([프로그래머스✈][연습문제] 3 x N 타일링 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qnfmtm666/프로그래머스연습문제-3-x-N-타일링-풀이-65hu8jij저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)