[백준] 11726 - 2xn 타일링

DP(Dynamic Programming) - 동적 프로그래밍

데이터 값들을 배열에 저장해 필요할 경우 빼서 사용할 수 있는 알고리즘

피보나치 때 썼던 재귀함수와 비슷하지만 트리가 하위 Degree로 내려가면서 

이미 했던 연산을 중복 연산하지 않고 점화식 배열에 저장해 둔 값을 꺼내어 쓴다.

따라서 시간 복잡도가 줄어들며 메모리를 적게 쓸 수 있다는 장점이 있다.

문제 풀이

접근방식인 동적 프로그래밍을 처음 봤고 방식을 도출하지 못해 나동빈 알고리즘 강의 유튜브를 참고했다.

그럼에도 점화식 이해를 못하여 황진경코딩영재학원 채널에서 동일한 올림피아드 문제를 설명해주신 영상을 

보고 난 뒤에 완전히 이해할 수 있었다.

점화식은 dp[n] = dp[n-1] + dp[n-2] 이다.

주어진 타일 형태는 1x2, 2x1 두 가지 타일이고 채워야할 타일 크기는 2xn으로 세로 길이가 고정이다.

우선 n이 1, 2, 3, 4, 5...일 때를 직접 그림 그려본다. n = 5로 가정했을 때 패턴을 도출할 수 있는데,

소유한 타일 유형이 2개 뿐이기 때문에 경우의 수는 n = 4(5-1)일 때 2x1 타일을 각각 경우의 수에 추가한 값.

그리고 n = 3(5-2)일 때 1x2 타일을 각각 경우의 수에 추가한 값. 

위의 두 가지 밖에 없다. 그 밖에 경우의 수는 n = 4 나 n = 3의 경우의 수에 포함되기 때문에 구하지 않아도 된다.

n = 2 에 2x1 타일을 추가한 값은 n = 3 경우의 수에 포함되기 때문이다.

그래서 코드를 짜보면 두 가지로 방법으로 풀 수 있다. 차이점은 메서드를 활용하냐 마냐인데 뭘 잘못했는진 몰라도

메서드를 사용하면 백준 제출 시 시간초과라고 자꾸 떠서 for문을 이용해 메서드 없이 바로 출력하는 방식을 택했다.

---

1) for문 이용한 메서드 없이 바로 출력한 코드

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

public class Tiling_2xn_11726 {


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

        int num = Integer.parseInt(br.readLine());
        int[] dp = new int[num+1];
        dp[1] = 1;
        dp[2] = 2;



    //dp 알고리즘
        for(int i = 3; i <= num; i++) {
            if(dp[i] != 0) {
                dp[i] = dp[i];
            } else {
                //dp[num] = dp(n-1)함수로 설정해줘야만 재귀함수가 실행된다. 배열로 잡아주면 메서드가 실행되지 않기 때문에 제자리 값 0만 출력한다.
                dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
            }
        }
                //출력
                System.out.println(dp[num]);
    }
}

---

2) 메서드 만들어 출력한 코드

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

public class Tiling_2xn_11726 {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        //출력
         System.out.println(dp[num]);
        }
    
    public static int dp(int num) {
    	
        int[] dp = new int[num+1];
        
        if(num == 1) return 1;
        if(num == 2) return 2;
        
        if(dp[num] != 0) {
        	return dp[num];
        } else {
        	dp[num] = (dp(num-1) + dp(num-2)) % 10007;
            return dp[num];
        }
    	
       }
}