#[프로그래머스][연습문제] 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];
}

🔨 문제 후기

디피는 어렵다. 단순한 문제 일 수록 더욱 어렵다.

생각을 많이하고 시간을 많이 소요하는 문제들도 생각보다 많다.

화이팅!

Series

Algorithms

이 글은 "Algorithms" 시리즈의 1번째 기록입니다.

01 / 27
  1. 01#[프로그래머스][연습문제] 3 x N 타일링 풀이
  2. 02[프로그래머스][2019 kakao] 블록게임 해설
  3. 03[프로그래머스][2019 kakao] 길 찾기 게임 문제 해설
  4. 04[프로그래머스][2019 kakao] 무지의 먹방 라이브 문제 해설
  5. 05[프로그래머스][2019 kakao] 후보키 문제 해설
  6. 06[프로그래머스✈][2020 kakao] 자물쇠와 열쇠 문제 풀이
  7. 07[프로그래머스][2020 kakao] 기둥과 보 설치 문제 해설
  8. 08[프로그래머스✈][2020 kakao] 가사 검색 문제 풀이
  9. 09[백준🔉][16234] 인구이동 문제 해설
  10. 10[프로그래머스✈][2019 kakao 겨울 인턴십] 불량 사용자 문제 해설
  11. 11[프로그래머스✈][2020 kakao] 동굴 탐험
  12. 12[백준🔉][14501] 퇴사 문제 해설
  13. 13[프로그래머스✈][2017 카카오코드] 4단 고음 해설
  14. 14[프로그래머스✈][2019 kakao 겨울 인턴쉽] 징검다리 건너기 해설
  15. 15[프로그래머스✈][연습문제] 섬 연결하기 풀이
  16. 16[leetcode][15] 3sum 문제풀기!
  17. 17[leetcode][16] 3sum closet 문제풀기!
  18. 18[📣top interview question] Remove Duplicates from Sorted Array Solution 문제풀기!
  19. 19[📣top interview question] Best Time to Buy and Sell Stock II 문제풀기!
  20. 20[leetcode][30] Substring with Concatenation of All Words 문제풀기!
  21. 21[leetcode][31] Next Permutation 문제풀기!
  22. 22[leetcode][32] Longest Valid Parentheses 문제풀기
  23. 23[leetcode][40] Combination Sum II 문제풀기!
  24. 24[leetcode][42] Trapping Rain Water 문제풀기!
  25. 25[leetcode][43] Multiply Strings 문제풀기!
  26. 26[leetcode][44] Wildcard Matching 문제풀기!
  27. 27[leetcode][45] Jump Game II 문제풀기!
시리즈 전체 보기