문제

첫 번째 시도

로직

2칸의 개수를 jump라 하고 1칸의 개수를 walk라 하자.
처음에는 jump = n/2 이고 walk = n%2이다.
jump가 0이 될 때까지
(jump+walk)!/(jump)!(walk)!
위 식을 합에 더하고 jump -= 1 walk += 2 를 한다.

• 위 식은 확률과 통계 중 조합 공식이다.

코드

class Solution {
    private static final int MOD = 1234567;
    
    public long solution(int n) {
        long answer = 0;
        
        int jump = n/2;
        int walk = n%2;
        
        while (jump >= 0) {
            if (walk == 0 || jump == 0) {
                answer += 1;
            }
            else {
                answer = (answer + comb(jump + walk, walk)) % MOD;
            }
            jump -= 1;
            walk += 2;
        }
        
        return answer % MOD;
    }
    
    // 조합
    private long comb (int n, int k) {
        long numerator = getFac(n);
        long denominator = (getFac(k) * getFac(n - k)) % MOD;
        return (numerator / denominator) % MOD;
    }
    
    // 팩토리얼
    private long getFac (int num) {
        long mul = 1;
        for (int i = num; i > 1; i --) {
            mul = (mul*i) % MOD;
        }
        return mul%MOD;
    }
}

결과

두 번째 시도

로직

첫번째 로직은 1234567의 나머지를 이용하여 계산하는 과정에서 계속 잘못된 값이 도출되어 완전히 다른 방식인 다이나믹 프로그래밍을 이용하였다.
dp[i] = dp[i-1] + dp[i-2] 로 1 칸을 가거나 혹은 2칸을 뛰어서 도달할 수 있다.
이것을 반복한 후에 dp[n]의 값을 반환한다.

코드

class Solution {
    private static final int MOD = 1234567;
    
    public long solution(int n) {
        if (n == 1) return 1;
        
        long[] dp = new long[n+1];
        
        dp[1] = 1; // 1칸에 도달하는 방법 1가지
        dp[2] = 2; // 2칸에 도달하는 방법 2가지
        
        for (int i = 3; i < n+1; i ++) {
            dp[i] = (dp[i-1] + dp[i-2]) % MOD;
        }
        
        return dp[n];
    }
}

결과

깨달은 점

다이나믹 프로그래밍을 정확하게 알고 있지 않았고, 만약 알고 있었다고 해도 나는 이 문제를 보자마자 바로 다이나믹 프로그래밍을 써야겠다는 생각을 못했을 것 같다.
알고리즘에 대한 이론 공부가 부족함과 아직 단순한 문제를 제외하고는 문제 로직을 생각하는데 부족함이 많음을 깨달았다.