[BOJ] 11727 - 2xn 타일링 2 Java 풀이

풀이

문제 링크는 아래에 있다.

BOJ 11727 - 2xn 타일링 2

11726 2xn 타일링 문제에서 아주 조금 바뀐 문제이다.
11726 문제 풀이 포스트를 먼저 보는 것을 추천한다.

문제 풀이는 다음과 같다.

우리가 2 * n 길이의 타일을 만드는 방법은 다음과 같다.

1. n 길이의 타일은 n - 1 타일에 세로 타일 1개를 붙여서 만들 수 있다. (경우의 수 1가지)
2. n 길이의 타일은 n - 2 타일에 가로 타일 2개와 2*2타일 하나를 붙여서 만들 수 있다. (경우의 수 2가지)

따라서 n 길이의 타일에 들어간 전체 타일 개수를 memoization[n] 이라고 하면 다음과 같이 식을 만들 수 있다.

memoization[n] = memoization[n - 1] + memoization[n - 2] * 2

이런 식으로 우리는 n 길이의 타일에 들어간 전체 타일 개수를 구할 수 있다.

구현

import java.util.Scanner;

class Solution_11727 {
    private final int MAX_NUM = 1001;
    private final int input;
    private final long[] memoization;
    Solution_11727(int input) {
        this.input = input;
        memoization = new long[MAX_NUM];
        memoization[1] = 1;
        memoization[2] = 3;
    }

    public long getAnswer() {
        for(int i = 3; i <= input; i++) {
            if(memoization[i] != 0) {
                continue;
            } else {
                memoization[i] = (memoization[i - 2] * 2 % 10007 + memoization[i-1] % 10007) % 10007;
            }
        }
        return memoization[input];
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution_11727(new Scanner(System.in).nextInt()).getAnswer() % 10007);
    }
}

코드 구조는 다음과 같다.
Main 함수에 한줄로 써보고 싶어서 저런 식으로 작성을 했는데, 변수를 나눠서 작성하는게 더 보기 좋은 듯하다.
어쨌든 Main 클래스의 Main 함수에서는 입력과 출력만을 담당하며 모든 연산은 Solution에게 위임한다.

Solution 클래스의 구조는 다음과 같다.
입력을 저장할 필드와 배열의 최대크기를 정의하고, 문제의 결과를 memoization할 memoization 배열을 생성한다.

Solution 클래스의 생성자에서는 입력을 받아서 배열을 초기화 한다.
답은 getAnswer()에서 연산한다.

getAnswer()는 for문으로 입력에 대한 memoization 배열의 부분문제들을 풀기 시작한다.
기본적인 틀은 위에서 썼던 memoization[n] = memoization[n - 1] + 2 * memoization[n - 2]이다.
그러나 문제에서 해당하는 값을 10007로 나눈 나머지를 구하라고 했기 때문에 위와 같은 식으로 변형되었다.
아마 문제의 답이 int 범위 최대치인 21억을 넘어가기 때문에 문제에서 저런 식으로 답을 제시한 듯 하다.
나머지를 구하는 식이 조금 특이한데, (a + b)%c = (a%c + b%c)%c와 같다고 한다.
이것은 추후에 따로 증명을 해볼 듯 하며, 우선 해당하는 식은 자주 사용되므로 외우는 것을 추천한다.

이렇게 답을 구하고 getAnswer()는 memoization[input]값을 반환한다.

풀이 결과