[프로그래머스] 멀리 뛰기 - Java

문제: https://programmers.co.kr/learn/courses/30/lessons/12914

코딩테스트 연습 - 멀리 뛰기

풀이과정

문제를 서술하는 방식만 바뀌었을 뿐, 2N 타일링 문제와 완전히 동일한 문제이다.

그래서 1칸 점프와 2칸 점프를 각각 다음과 같이 치환하여 생각할 수 있다.

이제, 높이가 2이고 가로길이가 N인 공간에 크기가 1 * 2인 타일을 놓는 방법의 수를 몇가지 더 찾아보면 다음과 같다.

이 그림을 보면 n = 3일 때와 n = 4일 때 각각 다음과 같은 규칙을 찾을 수 있다.

    1. n = 3일 때

    2. n = 4일 때

이를 정리하면, 어떤 임의의 양의 정수 n이 주어졌을 때 n칸 만큼 타일을 놓을 수 있는 방법의 수는

• n - 1칸까지 타일을 놓은 후 세로로 세운 타일을 하나 놓는 방법
• n - 2칸까지 타일을 놓은 후 가로로 눕힌 타일을 두개 놓는 방법

으로 나눌 수 있다.

 

따라서, n칸까지 타일을 놓는 방법의 수는 (n - 1)칸 까지 타일을 놓는 방법의 수 + (n - 2)칸 까지 타일을 놓는 방법의 수 가 된다.

 

소스코드

class Solution {
    public long solution(int n) {
        long[] answers = new long[n + 1];
        answers[0] = 1L;
        answers[1] = 2L;
        for (int i = 2; i < n; i++) {
            answers[i] = (answers[i - 1] + answers[i - 2]) % 1234567;
        }

        return answers[n - 1];
    }
}