[프로그래머스] 2 x n 타일링

코드 힌트:

1. 규칙 찾기:
   • 문제는 2xN 크기의 직사각형을 채우는 방법의 수를 구하는 것입니다.
   • 가로 길이가 2, 세로 길이가 1인 타일을 사용합니다. 이 타일로 주어진 공간을 채울 수 있는 방법의 수를 계산합니다.
   • n = 4일 때:
     • 1111 => 1가지
     • 112 => 3가지 (112, 211, 121)
     • 22 => 1가지 (22)
   • n = 5일 때:
     • 11111 => 1가지
     • 1112 => 4가지 (1112, 2111, 1211, 1121)
     • 122 => 3가지 (122, 212, 221)
   • 이러한 패턴을 보면, 각 n에 대한 타일링 방법의 수는 피보나치 수열과 동일하다는 것을 알 수 있습니다.
   • 저는 조금 더 확실하게 하기 위해 7까지 하고 풀어봤었습니다. 예시는 길어지니 5까지 하겠습니다.
2. 피보나치 알고리즘으로 풀기:
   • 이 문제는 피보나치 수열을 사용하여 해결할 수 있습니다. n번째 타일링 방법의 수는 f(n) = f(n-1) + f(n-2)로 구할 수 있습니다.
   • 주의할 점은 큰 수를 다루기 때문에, 결과를 1000000007로 나눈 나머지를 사용해야 합니다.
   • 반복문을 사용해 n번째 피보나치 수를 구할 수 있으며, 이 때 이전 두 값을 기억하면서 연산하면 됩니다.

 

 

---

정답은 더보기 클릭

class Solution {
    // 피보나치 수열의 n번째 값을 구하는 문제
    // 단, 결과는 1000000007로 나눈 나머지를 반환
    public int solution(int n) {
        // 초기 피보나치 수열의 첫 두 값을 설정
        int[] arr = {1, 1};
        
        // n이 1보다 큰 경우, n번째 피보나치 수를 구하기 위해 반복
        while (n > 1) {
            n--;  // n번째 값을 계산할 때마다 n을 감소
            
            // 새로운 피보나치 수를 계산, 모듈로 연산으로 overflow 방지
            int tmp = (arr[0] + arr[1]) % 1000000007;
            
            // 이전 두 값을 업데이트
            arr[0] = arr[1];  // arr[1] 값을 arr[0]로 이동
            arr[1] = tmp;     // 새로 계산한 피보나치 수를 arr[1]로 이동
        }
        
        // n번째 피보나치 수 반환
        return arr[1];
    }
}