프로그래머스 연습문제 2 x n 타일링 [JAVA] - 22년 9월 9일

처음에 그냥 조합으로 풀려고 했는데 오버플로우 때문에 런타임 에러가 계속 발생 , 아무리 생각해도 모르겠어서 정답을 참고하니 DP문제 였다...
DP 문제인걸 알고 나서도 이게 왜 DP인지 한참을 고민했던것 같다.
나만의 정의를 내려서 DP로 풀기는 했지만 역시 DP는 많이 풀어보는게 장떙인것 같다.

package com.company;

// 참조 : https://school.programmers.co.kr/questions/10368
// 참조 : https://deveric.tistory.com/61

class Solution {
    //Combination nCr = n! / (r! * (n-r)!) 으로 처음에 풀었으나 overFlow 때문에 계산이 되지 않음
    //피보나치 수열로 접근을 해야한다.
    //DP 문제 , 메모이제이션 접근
    public int solution(int quizNum) {
        long[] memo = new long[quizNum + 1];

        memo[1] = 1;
        memo[2] = 2;

        for (int i = 3; i <= quizNum; i++) {
            memo[i] = (memo[i-1] + memo[i-2])% 1000000007;
        }

        return (int) (memo[quizNum]);
    }
}