[백준] 2xn 타일링 1, 2

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

 

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

 

세트처럼 생긴 두 문제를 풀어보았다.

쉬운 DP 문제라고 해서 덤볐는데 생각보다 빨리 못풀었다.

 

두문제 다 내가 몇년전에 다른 언어로 풀었던기 기록이 있던데

그땐 어떻게 풀었나 모르겠다 ㅎㅎ

 

우선 두 문제 모두, 문제 풀이 방법은 못풀고 고민했던 시간이 아까울 정도로 아주 간단했다.

 

n=1일 때부터 경우의 수를 모두 따져보고 점화식을 세우기만 하면 된다.

 

2xn 타일링의 경우,

모든 경우의 수를 따져보면 이렇다.

n=1 : 1가지
n=2 : 2가지
n=3 : 3가지 (= 1 + 2)
n=4 : 5가지 (= 2 + 3)
n=5 : 8가지 (= 3 + 5)
...

피보나치와 동일한 규칙이다.

즉 2xn 타일링 문제는 피보나치 수를 구하는 문제와 같은 문제이다.

 

제출코드

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

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

        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }
        System.out.println(dp[n]);
    }
}

 

 

 

2xn 타일링 2의 경우,

똑같이 모든 경우의 수를 따져보면 아래와 같다.

n=1 : 1가지
n=2 : 3가지
n=3 : 5가지 (= 1*2 + 3)
n=4 : 11가지 (= 3*2 + 5)
n=5 : 21가지 (= 5*2 + 11) 
n=6 : 43가지 (= 11*2 + 21)
...

잘 보면 규칙이 보인다.

처음에는 n=4일 때와 n=5일 때의 경우의 수를 잘못 구해서 규칙을 계속 못찾았었다.

항상 경우의 수를 정확히 따지도록 노력해야겠다.

 

제출 코드

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

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

        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2] * 2) % 10007;
        }
        System.out.println(dp[n]);
    }
}