백준 - 타일링 문제들- DP - Java

1.📌 [2*n 타일링] 문제

문제: https://www.acmicpc.net/problem/11726

📢똑같은 문제가 프로그래머스에도 있었다.
프로그래머스 2 X n 타일링 https://school.programmers.co.kr/learn/courses/30/lessons/12900

참고 풀이 - 블로그
참고 풀이 - 유튜브

결국 DP는 점화식을 어떻게 세우는지가 관건이다. 점화식 세우는 것은 결국 풀어보는 것 밖에 없는 것 같다.

[백준 [2*n 타일링]] 코드

import java.util.*;
import java.io.*;

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] = 2;
        
        for(int i = 3; i <= N; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }
        
        System.out.println(dp[N]);
    }
}

[프로그래머스 [2Xn 타일링]] 코드

class Solution {
    public int solution(int n) {
        long dp[] = new long[n+1];
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i = 3; i <= n; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
        }
        return (int)dp[n];
    }
}

2. 📌 [2×n 타일링 2] 문제

문제: https://www.acmicpc.net/problem/11727

위에 풀이와 비슷하다. 그냥 경우의 수가 달라진 걸 뿐.

import java.util.*;
import java.io.*;

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-1] + 2 * dp[i-2]) % 10007;
        }
        
        System.out.println(dp[N]);
    }
}

3. 📌[타일링] 문제

문제: https://www.acmicpc.net/problem/2133

이 문제는 3 X N의 타일전체를 1 X 2, 2 X 1의 타일로 채우는 문제이다.

✨핵심 포인트

N이 홀수일때는 아무것도 채울 수 없다는 것이다. = 0
따라서 dp[0] = 1, dp[1] = 0인 것이다.

• 짝수일때는 고유의 경우의 수가 2개씩 있으므로 2개씩 곱해준다.

import java.util.*;
import java.io.*;

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[31];
        
        dp[0] = 1;
        dp[1] = 0;
        dp[2] = 3;
        
        for(int i = 3; i <= N; i++){
            dp[i] = (3 * dp[i-2]);
            
            for(int k = 3; k <= i; k++){
                if(k % 2 == 0){
                    dp[i] += 2 * dp[i - k];
                }
            }
        }
        
        System.out.println(dp[N]);
    }
}

4. 📌[타일 채우기3] 문제

문제: https://www.acmicpc.net/problem/14852

참고 풀이

✨핵심 Point

%값이 크기 때문에 배열을 long으로 해줘야 한다.

import java.util.*;
import java.io.*;

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());
        
        long dp[][] = new long[1000001][2];
        
        dp[0][0] = 1;
        dp[1][0] = 2;
        dp[2][0] = 7;
        dp[2][1] = 0;
        
        for(int i = 3; i <= N; i++){
            dp[i][1] = (dp[i - 3][0] + dp[i-1][1]) % 1000000007;
            dp[i][0] = (2 * dp[i-1][0] + 3 * dp[i-2][0] + 2 * dp[i][1]) % 1000000007;
        }
        
        System.out.println(dp[N][0]);
    }
}