[PRG] 12902 3 x n 타일링 JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/12902

프로그래머스

 

메모리: 52.2 MB

실행시간: 4.09 ms

 

문제분석

세로의 길이가 3으로 정해져 있다.

한 칸에 들어갈 수 있는 모양은 ⊂, ⊃, ∪, ∩ 이렇게 총 4개이다.
그렇다면 1행 당 4^n의 경우의 수가 나온다. 이때, 바로 직전의 행만 확인하면 되므로 총 3행일 경우 O(3*4^2n)의 시간복잡도를 갖는다.
따라서, n이 작을수록 효율적이기 때문에 직사각형을 90도 돌려서 타일링한다. 

이때 고려할 점,

1. 이전 행에서 현재 행에 영향을 미치는 모양은 ∩ 뿐이다. -> 이전 행이 ∩일 경우 무조건 ∪만 가능, 이외는 모든 모양 가능
2. 따라서 ∩을 제외한 모양은 ㅁ이라고 치환한다.
3. 1번째 행의 경우 ∪ 모양은 유효하지 않다.
4. n번째 행의 경우 ∩ 모양은 유효하지 않다.

 

걸린시간

1시간 ⏱️

 

풀이방법

1. ∩를 1, ㅁ을 0으로 치환한다.
2. 1행씩 내려가면서 DP연산을 수행한다.
3. 인덱스를 비트연산으로 치환한다. ex) 000, 001, ... , 111 (모든 경우의 수)
4. 1번째 행을 채운다. 이때 1번째 행에 가능한 모양 -> ⊂⊃∩(001), ∩⊂⊃(100), ∩∩∩(111)
5. 따라서 현재 1행에 채워진 수는 [0, 1, 0, 0, 1, 0, 0, 1]
6. 2번째 행 부터는 이전 행과 유효한 타일을 찾아야 한다.

규칙1 : XOR연산을 통해 111이 나올 경우 유효하다.

ex ) ∩∩∩ (111)   ∩∪∩(101)
    ∪∪∪ (000) ∪∩∪(010)

규칙2 : 0이 연속될 경우 추가적으로 000과 유효하다. (반대의 경우도 유효)

ex) ∩⊂⊃ (100) ⊂⊃∩ (001)
   ∪⊂⊃ (000) ⊂⊃∪  (000)

7. 위 규칙을 통해 DP연산을 수행한다.
8. n번째 행에서는 유일한 경우인 000 만 체크한다.

 

포인트

1. 직사각형을 90도 회전해서 계산하며 효율을 높인다 !
2. 타일은 4가지 모양으로 분리하여 푼다 !
3. 바로 이전 행과의 조합 규칙을 찾는다 !

p.s. 이 풀이방법을 공유해 준 미나리씨 감사 ~~~~ ❤️

 

코드

class Solution {
    public int solution(int n) {
        // 효율적인 연산을 위해 직사각형을 90도 회전
        long[][] map = new long[n][8];    // 한 행에 나올 수 있는 경우의 수 8가지
        map[0][1] = map[0][4] = map[0][7] = 1;  // 1번째 행에서 가능한 경우
        // DP 연산
        for(int i = 0; i < n - 1; i ++) {
            for(int now = 0; now < 8; now ++) { // 인덱스 비트 연산
                map[i + 1][now ^ 7] += map[i][now] % 1000000007L; // 규칙 1
                if(now == 1 || now == 4) {  // 규칙 2
                    map[i + 1][0] += map[i][now] % 1000000007L;  
                }
                if(now == 0) {  // 규칙 2
                    map[i + 1][1] += map[i][0] % 1000000007L;
                    map[i + 1][4] += map[i][0] % 1000000007L;
                }
            }
        }
        // n행의 유일한 유효값인 000에 저장된 결과값 반환
        return (int) (map[n - 1][0] % 1000000007L);
    }
}