99클럽 코테 스터디 19일차 TIL + 오늘의 학습 키워드

오늘의 학습내용

• dp (다이나믹 프로그래밍)
• 재귀함수

오늘의 회고

코드의 실행시간을 최적화 할 3가지 방법은 다음과 같다.

1. 더 빠르게 처리할 수 있는 과정이 있는가?
2. 불필요한 정보를 구하기 위해 시간을 소비하고 있는가?
3. 이미 알고 있는 정보를 구하기 위해 시간을 낭비하고 있지 않는가?

문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

내 풀이 (여러 번의 시도,,)

• 첫번째 시도

단순히 조합문제로 접근했다.
예를 들어 4라고 할때
4
=> 2 + 2
=> 2 + 1 + 1
=> 1 + 1 + 1 + 1
이므로 결국 2의 개수와 1의 개수는 2의 몫에 따라 영향을 받는다고 생각했다.
만약 2의 개수와 1의 개수를 안다면 거기서 나오는 방법 가짓수는 중복된 숫자를 포함한 순열로 볼 수 있다. 따라서 팩토리얼 함수를 새로 만들고 그에 따른 answer에 대해 구현해보았는데 결정적으로 factorial 함수가 메모리초과를 일으키는 원인이 되었다..

import java.util.*;

class Solution {
    private static int M = 1234567;
    public static long solution(int n){
        long answer = 0;
        int quo2 = n / 2;
        for(int i=0; i<=quo2; i++){ //2의 몫이 0~B일 때까지
            int quo1 = n - 2*i;
            int sumOf2 = n - i;
            answer += (factorial(sumOf2)) / (factorial(quo1) * factorial(i));
        }

        return answer;
    }
    public static long factorial(int K){
        long ans = 1;
        for(int i=1; i<=K; i++){
            ans *= i;
        }
        return ans;
    }
}

• 두번째 시도

dp를 이용한 풀이

아래 코멘트는 두번째 시도를 한 후에도 에러가 나서 질문방을 찾던중 찾은 답변이다 ㅠㅠ

arr[i]=arr[i-1]+arr[i-2];를 할 때마다 나머지 연산을 해주지 않으면 오버플로가 나지 않을까 싶네요 : )

두번째 시도에서는 다음과 같이 했는데 또다시 런타임에러가 발생했다. 고민을 해보던중 만약 n=1이라면? dp 배열의 크기는 2가 되며 dp[2]에 접근할 때 ArrayIndexOutOfBoundsException이 발생한다는 것을 깨달았다. 즉, dp의 크기는 2인데 dp[2]에 대해 정의할 수 없다는 것이다.

import java.util.*;

class Solution {
    static int M = 1234567;
    public static long solution(int n){
        long[] dp = new long[n+1];
        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3; i <= n; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % M;
        }

        return dp[n];
    }
}

• 마지막 시도

그에 대한 해결책으로 n==1 인 경우와 n==2인 경우를 추가하여 indexOutOfRange에러를 해결할 수 있었다.

import java.util.*;

class Solution {
    static int M = 1234567;
    public static long solution(int n){
        if (n == 1) return 1;
        if (n == 2) return 2;

        long[] dp = new long[n+1];
        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3; i <= n; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % M;
        }

        return dp[n];
    }
}