[백준] 11727 2xn 타일링_Java

📖  문제

---

백준 11727

11727번: 2×n 타일링 2

2022.03.01 - [[Java] 백준 문제풀이/DP] - [백준] 11726 2xn 타일링_Java

위 게시글에서 2x2 도형이 추가 된 버전이다. 코드는 많이 다를게 없으며 점화식을 찾아야 한다.

 

dp[n]=dp[n−1]+2×dp[n−2]

⚠️  주의사항

---

• 만들어지는 경우의 수를 뽑는게 아닌 10007로 나눈 나머지값을 출력

 

✍️  이해

---

/**
 * ====================================
 * DFS 풀이
 * 11726 버전에서 2x2 도형이 추가 됨
 *
 * 2칸을 쓰는 2x2 도형
 * 2칸을 쓰는 1x2 도형
 * 1칸을 쓰는 2x1 도형
 *
 * 이 3가지의 경우가 있다는 것을 생각하고 문제를 풀기
 * ====================================
 * DP풀이
 * 점화식 만들어서 풀기
 * ====================================
 */

✏️  풀이

---

DFS 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int[] answer;
    public int solution(int n) {
        if(answer[n] > 1) return answer[n];
        else if(n == 1) return answer[n] = 1;
        else if(n == 2) return answer[n] = 3;

        return answer[n] = (solution(n - 2) * 2 + solution(n - 1)) % 10007;

        //return answer[n] = (solution(n - 2) + solution(n - 2) + solution(n - 1)) % 10007;
        // 2칸을 쓰는 2x2 도형
        // 2칸을 쓰는 1x2 도형
        // 1칸을 쓰는 2x1 도형
    }


    public static void main(String[] args) throws IOException {
        Main T = new Main();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        answer = new int[n + 1];

        System.out.println(T.solution(n));
    }
}

DP 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[1001];

        dp[1] = 1;
        dp[2] = 3;

        for (int i = 3; i <= n; i++) dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % 10007;

        System.out.println(dp[n]);
    }
}

---

1번 = dp 풀이 // 4번 DFS 풀이 // 2,3번 dp풀이 중 dp 배열 초기화를 잘못해서 생긴 오류