DP - 11726 (2xn 타일링)

본 문제는 2xn 타일링 문제입니다. 이 문제의 핵심은 적절한 점화식을 찾아내는 것입니다.

11726번: 2×n 타일링 (acmicpc.net)

11726번: 2×n 타일링

우선 그림으로 타일들을 나타낸다면,

다음과 같은 패턴을 볼 수 있습니다. 이 경우에 점화식을 찾아내게 된다면 

 

F(n) = F(n-1) +F (n-2) 의 점화식을 구할 수 있고 이를 이번에는 재귀함수를 통해서 TOP-DOWN 방식을 통해 풀어내게 된다면, 다음과 같은 코드가 나오게 됩니다.

package com.company;

import java.util.Scanner;

public class Main {
    static int result[] = new int[1001];

    public static int domino(int n){

        result[0] = 1;
        result[1] = 1;
        result[2] = 2;

        if(result[n] != 0){
            return result[n];
        }
        else{
            result[n] = (domino(n-1) + domino(n-2))%10007;
        }

        return result[n];
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(domino(n)%10007);

    }
}

이와 연계 하여서 11727문제도 점화식 변경하는 식으로 풀어냈습니다. 

11727번: 2×n 타일링 2 (acmicpc.net)

11727번: 2×n 타일링 2

부족했던 점

처음 시도를 하였을때는 아래의 코드와 같이

package com.company;

import java.util.Scanner;




public class Main {
    static int result[] = new int[1001];

    public static int domino(int n){

        result[0] = 1;
        result[1] = 1;
        result[2] = 2;
        if(n == 0) return result[0];
        if(n == 1) return result[1];
        if(n == 2) return result[2];


        result[n] = (domino(n-1) + domino(n-2))%10007;


        return result[n];
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(domino(n)%10007);

    }
}

이미 결과값을 구한 배열일때도 연산을 다시 하도록 해주서어서 시간이 더 오래걸려 시간제한조건을 충족하지 못했습니다. 이를 해결하기 위해서 점화식 결과값을 리턴하기전 다음과 같은 조건을 삽입해주 이미 배열속에 값이 있는 경우에는 바로 값을 리턴해주도록 하였습니다. 

        if(result[n] != 0){
            return result[n];
        }