[baekjoon #11726] 2×n 타일링

dp를 이해하는데 가장 기본이 되면서 중요한 문제가 아닐까 싶다.

 

dp는 기본적으로 bottom-up 방식을 선호하는데

차례차례 적다보면 규칙이 보이기 때문이다.

이게 쉽게 찾아지냐 안 찾아지냐의 차이에 따라서 dp의 난이도가 결정되는 것 같다.

 

이 문제 같은 경우는 

n-1과 n-2를 통해서 n을 찾는 문제이다.

n-1 경우에 한 개를 더 붙인 경우, n-2 경우에 두 개를 더 붙인 경우라고 가정하고 풀면

n의 경우가 나오게 되는 걸 알 수 있다.

 

실제로 n=4의 경우의 수를 그려보고

n=3과 n=2의 경우를 그려보고 막대기를 갖다댄다면 4의 경우수만큼 그릴 수 있다.

 

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

 

 

 

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?