[백준] 11726번: 2×n 타일링 - JAVA

🔗 문제 링크

BOJ 11726번: 2×n 타일링

11726번: 2×n 타일링

 

📝 풀이 과정

문제를 보고 경우의 수를 하나씩 그려보기로 했다.

 

n = 4까지 그리고 난 뒤 확인해보면 일정한 패턴이 반복됨을 알 수 있었다.

 

노란색으로 체크된  n - 1의 타일에 세로 타일이 하나 추가된 모습이고,

파란색으로 체크된 n - 2의 타일에 가로 타일이 두 개 추가된 형태를가지고 있다.

 

따라서, $dp[n] = dp[n-1] + dp[n-2]$라는 점화식을 가지게 된다.

 

💡 mod 연산을 한 결과값을 출력해야 할 때에는 반드시 연산할 때마다 mod 연산을 해주어야 한다. 계속 숫자를 더하고 마지막 출력시에만 mod연산을 해줄 경우 Integer.MAX_VALUE를 넘어 Overflow가 발생하기 때문에 잘못된 값이 출력될 수 있다.

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        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]);

    }
}

 

📊 제출 결과