코딩 테스트 - 3 x n 타일링

package programmers;

import java.util.stream.IntStream;
public class _3_x_n_타일링_230618 {

    /*
    동적 계획법(Dynamic Programming)을 사용하여 문제를 해결합니다.

    해당 문제는 3 x n 크기의 바닥을 2 x 1 크기의 타일로 채우는 방법의 수를 구하는 문제입니다.
    직사각형 타일은 가로로 배치하거나 세로로 배치할 수 있습니다.

    해당 코드에서는 동적 계획법을 활용하여 문제를 해결합니다.
    우선, 가로의 길이가 1인 경우는 2가지 방법이 가능하므로 dp[1]은 2로 초기화합니다.
    가로의 길이가 2인 경우는 3가지 방법이 가능하므로 dp[2]는 3으로 초기화합니다.

    이후, dp[i]는 dp[i-1]과 dp[i-2]의 값을 활용하여 계산됩니다.
    i가 짝수인 경우(i%2 == 0)에는 이전의 경우의 수(dp[i-1]과 dp[i-2])를 더해서 계산합니다.
    i가 홀수인 경우에는 dp[i-1]의 경우의 수에 2를 곱하고 dp[i-2]의 경우의 수를 더해서 계산합니다.

    마지막으로, dp[i]를 1000000007로 나눈 나머지를 구하여 저장합니다.
    이는 문제에서 요구하는 방법의 수를 구하는 과정에서 숫자가 매우 커지는 것을 방지하기 위함입니다.

    마지막으로, dp[n]을 반환하여 주어진 n에 대한 방법의 수를 출력합니다.

    예를 들어, n이 8인 경우를 예로 들면, dp[1]과 dp[2]는 이미 초기화되어 있고,
    dp[3]부터 dp[8]까지의 값을 계산하여 결과를 반환합니다.
    최종적으로 dp[8]의 값인 22를 반환합니다.
    */
    public int solution(int n) {
        int answer = 0;
        int mod = 1000000007; //경우의 수를 나누려는 숫자

        int[] dp = new int[n+1];

        dp[1] = 2;
        dp[2] = 3;

        for(int i = 3; i <= n; i++){
            if(i%2 == 0){
                //짝수
                dp[i] = dp[i-1]%mod + dp[i-2]%mod;
            } else {
                // 홀수
                dp[i] = dp[i-1]*2%mod + dp[i-2]%mod;
            }
            dp[i] = dp[i]%mod;
        }
        return dp[n];
    }



    //아래 풀이는 시간 초과가 납니다.

    /*
    IntStream.rangeClosed(4, n): 4부터 n까지의 정수들로 이루어진 스트림을 생성합니다.
    이 스트림은 4부터 n까지의 값을 가지고 있습니다.

    filter(i -> i % 2 == 0): 스트림의 요소 중에서 짝수인 요소들만을 필터링합니다.
    짝수인 경우에만 타일을 배치하므로, 홀수인 요소는 건너뜁니다.

    forEach(i -> { ... }): 각 요소에 대하여 수행할 동작을 정의합니다.
    여기서는 tile[i]를 계산하고 저장하는 역할을 합니다.

    IntStream.rangeClosed(0, i - 4): 0부터 (i - 4)까지의 정수들로 이루어진 스트림을 생성합니다.
    이 스트림은 0부터 (i - 4)까지의 값을 가지고 있습니다. 이는 세로로 배치된 타일의 개수에 해당합니다.

    filter(j -> j % 2 == 0): 스트림의 요소 중에서 짝수인 요소들만을 필터링합니다.
    짝수인 경우에만 세로로 배치된 타일의 개수를 고려합니다.

    mapToLong(j -> tile[j] * 2): 짝수 인덱스 j에 대하여 tile[j]의 값을 가져와 2를 곱합니다.
    이는 세로로 배치된 타일의 개수에 해당하는 tile[j] 값을 가져오고, 2를 곱하여 가로로 배치된 타일의 개수에 더해줍니다.

    sum(): 계산된 값들의 합을 구합니다. 이는 세로로 배치된 타일과 가로로 배치된 타일의 개수를 합친 값을 의미합니다.

    tile[i] %= mod: 계산된 tile[i]의 값을 mod로 나눈 나머지로 갱신합니다. 이는 경우의 수가 매우 커질 수 있으므로,
    나머지 값을 사용하여 문제 조건에 맞게 결과를 반환합니다.

    return tile[n]: 최종적으로 tile[n]의 값을 반환합니다. 이는 가로의 길이가 n인 바닥을 채우는 방법의 수를 의미합니다.
     */
    long[] tile = new long[5001];

    public long solution_timeout(int n) {
        int mod = 1_000_000_007;

        tile[0] = 1;
        tile[2] = 3;

        // 4부터 n까지의 짝수에 대해 반복
        IntStream.rangeClosed(4, n)
                .filter(i -> i % 2 == 0) // 짝수 필터링
                .forEach(i -> {
                    // tile[i]를 계산
                    tile[i] = tile[i - 2] * 3 + IntStream.rangeClosed(0, i - 4)
                            .filter(j -> j % 2 == 0) // 짝수 필터링
                            .mapToLong(j -> tile[j] * 2) // 짝수 인덱스의 tile[j]에 2를 곱함
                            .sum(); // 계산된 값들의 합을 구함
                    tile[i] %= mod; // 나머지 연산
                });

        return tile[n]; // tile[n] 반환
    }


}