8월 12일 99클럽 항해 22일

99클럽 항해 22일차

 

오늘의 문제는 멀리 뛰기이다.

 

홀수의 경우 i는 n을 2로 나눈 몫으로 설정하고 ∑(n-k)Ck가 1부터 i까지로 생각하고 조합의 합을 구하고.

짝수의 경우 홀수의 경우에서 +1을 해서 조합의 합을 구하려고 했으나 

class Solution {
    public long solution(int n) {
        int count = n / 2;
        int check = n % 2;
        long answer = 1;

        for (int i = 1; i <= count; i++) {
            answer += comb(n - i, i);
            n=n-2;
        }

        if (check == 0) {
            answer += 1; 
        }
        answer%=1234567;

        return answer;
    }

    public long fact(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * fact(n - 1);
    }

    public long comb(int n, int i) {
        if (i > n) return 0;
        return fact(n) / (fact(n - i) * fact(i));
    }
}

 

시간초과와 일부 오답으로 생각을 처음부터 다시하게 되었다. 저번 문제도 동적계획법을 사용했었기 때문에 이번에도 비슷한 방식으로 생각을 하게 되었고, 문제는 dp[i] = dp[i-1]+dp[i-2]의 점화식을 따르는 구조임을 알 수 있고, 오류를 방지하기 위해서 dp[1], dp[2]의 값을 미리 입력해준다.

class Solution {
 
    public long solution(int n) {
        long[] answer = new long[2001];
        answer[1] = 1;
        answer[2] = 2;
 
        for (int i = 3; i < 2001; i++) {
            answer[i] = (answer[i - 1] + answer[i - 2]) % 1234567;
        }
 
        return answer[n];
    }
}