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

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

프로그래머스

문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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하면 됩니다.

 

풀이

끝에 도달하는 방법의 가짓수를 return 하는 문제이다.

문제를 보고 조금 고민해 보니 피보나치 수열이라는 것을 알 수 있었다.

1번째 칸까지 가는 경우 : 1
2번째 칸까지 가는 경우 : 2 (1칸, 1칸), (2칸)
3번째 칸까지 가는 경우 : 3 (1칸, 1칸, 1칸), (1칸, 2칸), (2칸, 1칸)
4번째 칸까지 가는 경우 : 5  (1칸, 1칸, 1칸, 1칸), (1칸, 2칸, 1칸), (1칸, 1칸, 2칸), (2칸, 1칸, 1칸), (2칸, 2칸)

 

생각해 보면, 3번째 칸까지 가는 경우는 <1번째 칸까지 간 후 2칸을 가는 경우> + <2번째 칸까지 간 후 1칸을 가는 경우>로 나뉜다는 것을 알 수 있다.

따라서 3번째 칸까지 가는 경우 = 1번째 칸까지 가는 경우 + 2번째 칸까지 가는 경우라고 할 수 있다.

 

문제 이해를 한 후 구현하는 것은 어렵지 않았는데, 다른 사람들의 풀이를 보니 조금 더 간단히 풀 수 있을 것 같다는 생각이 들어 3단계에 거쳐 코드를 변경해 보았다.

 

---

🔔 문제를 해결한 코드 1, 2

코드 1

n1 : 홀수 단계, n2 : 짝수 단계
n = 1, 2일 때는 바로 return
n >= 3일 경우 : 홀수일 때는 n1을, 짝수일 때는 n2를 증가시키며 답을 갱신하였다.

class Solution {
    public long solution(int n) {
        long answer = 0;
        
        int n1 = 1;
        int n2 = 2;
        
        if(n == 1) return 1;
        if(n == 2) return 2;
        
        for(int i = 3; i <= n; i++) {
            answer = (n1 + n2) % 1234567;
            
            if(i % 2 == 1) n1 += n2;
            else n2 += n1;
            
            n1 %= 1234567;
            n2 %= 1234567;
        }
        
        return answer;
    }
}

 

코드 2

pre : 이전 단계, tmp : answer 저장용 변수
n = 1, 2일 때는 바로 return
n >= 3일 경우 : 이전 답 + 현재 답을 하여 답을 갱신하였다.

class Solution {
    public int solution(int n) {
        int answer = 2;
        
        int pre = 1;
        int tmp = 2;
        
        if(n == 1) return 1;
        if(n == 2) return 2;
        
        for(int i = 3; i <= n; i++) {
            tmp = answer;
            answer = (answer + pre) % 1234567;
            pre = tmp;
        }
        
        return answer;
    }
}

---

코드

코드 2에서 n = 1, 2일 경우와 n >=3일 경우를 합쳤다.

class Solution {
    public int solution(int n) {
        int answer = 1;
        
        int pre = 0;
        int tmp = 1;
        
        for(int i = 1; i <= n; i++) {
            tmp = answer;
            answer = (answer + pre) % 1234567;
            pre = tmp;
        }
        
        return answer;
    }
}

 

틀린 부분이 있다면 정정해 주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!