[PRG] 12900 2 x n 타일링 JAVA

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

프로그래머스

 

메모리: 54.7 MB

실행시간: 9.43 ms

 

문제분석

3 x n 타일링과 똑같은 문제 !!
규칙만 업데이트하면 된다 😎

 

걸린시간

20분 ⏱️

 

풀이방법

https://yeahzzz.tistory.com/95

[PRG] 12902 3 x n 타일링 JAVA

위 링크를 타고 가시면 자세한 풀이 방법이 나와있습니다 ㅎㅎ

여기서는 좀 더 단순화 시킬 필요가 있다
왜냐면... 효율 테스트가 꽤나 까다롭다 ^^... n범위가 보다 넓어졌기 때문에 ....

이번에는 00	01	10	11 을 비트연산 했을 때
전부 XOR만 유효하고, 00과 00만 예외적으로 유효하다는 규칙을 발견할 수 있었다 !

결국 인덱스로 봤을 때,
0 - 0, 0 - 3, 1 - 2 이렇게 서로 유효하다.

하지만, 첫 행에서 1, 2는 유효하지 않기 때문에 결국 끝까지 유효하지 않게 된다.
따라서, 0과 3인덱스만 연산해준다 !

위 조건에 따라 DP연산 해주면 된다 !

 

포인트

형변환을 잘해야 합니다 ^~^
큰 수는 잊지 말고 long 사용하기 ~~~~~~ 🥲

 

코드

※ 너무 간단한 코드라 주석은 따로 달지 않았습니다 !

class Solution {
    public int solution(int n) {
        long[][] map = new long[n][4];
        map[0][0] = map[0][3] = 1;
        
        for(int row = 0; row < n - 1; row ++) {
            map[row + 1][0] += (map[row][3] + map[row][0]) % 1000000007L;
            map[row + 1][3] += map[row][0] % 1000000007L;
        }
        return (int) (map[n - 1][0] % 1000000007L);
    }
}