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

풀이

문제 링크는 아래에 있다.

BOJ 11726 - 2xn 타일링

생각하는 방식을 조금 다르게 생각했어야 했던 것 같다.

혼자 풀이를 하다가 특정 부분에서 막혀서 풀이를 보게 되었다.

처음 생각했던 풀이는 다음과 같았다.

이 문제는 다이나믹 프로그래밍으로 풀 수 있다고 생각했다.
가로의 길이가 n인 타일은 n - 1의 타일짜리에 세로 타일 하나를 붙인 것이거나 n - 2 타일짜리에 가로 타일 2개를 붙인 것과 같기 때문이었다.
즉, 이전에 풀었던 부분문제의 결과를 다시 풀어야 하고, 이것은 메모이제이션 기법으로 저장해두고 꺼내서 쓰면 효율을 높일 수 있다.
이러한 문제들은 전형적인 다이나믹 프로그래밍 문제의 특징이라고 볼 수 있다.

또한 TMI인데, 다이나믹 프로그래밍 문제들을 풀 때, 그리디 알고리즘으로 풀 수 있는 경우가 있다.
정확한 이유는 아직 모르나, 알게되면 추후에 정리를 해보고 싶다.

어쩄든 문제 풀이 과정은 다음과 같이 생각했다.

처음에는 타일 길이가 1인 경우와 타일길이가 2인 경우부터 생각을 했다.
그리고 타일길이가 3인 경우를 생각했는데, 1인 경우에서 3인 경우를 만들 때 세로가 3개 있는 경우가 두번이 나오는 식으로 생각을 하였다.
즉 이부분에 대한 생각이 꼬여서 문제를 푸는게 잘 안됐었다.

참고한 다른 풀이는 다음과 같다.

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

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

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

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

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

구현

import java.util.Scanner;

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

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

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

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

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

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

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

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

풀이 결과