멀리 뛰기

· 문제 설명

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

 

· 제한 사항

n은 1 이상, 2000 이하인 정수입니다.

 

· 입출력 예

n	result
4	5
3	3

 

· 입출력 예 설명

입출력 예 #1
위에서 설명한 내용과 같습니다.
입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

---

· Thinking 1

1칸일때 1 (1)
2칸일때 2 (1, 1) (2)
3칸일때 3 (1, 1, 1) (2, 1) (1, 2)
4칸일때 5 (1, 1, 1, 1) (2, 1, 1) (1, 2, 1) (1, 1, 2) (2, 2)
5칸일때 8 (1, 1, 1, 1, 1) (2, 1, 1, 1) (1, 2, 1, 1) (1, 1, 2, 1) (1, 1, 1, 2) (2, 2, 1) (1, 2, 2) (2, 1, 2) 
6칸일때 13 (1, 1, 1, 1, 1, 1) (2, 1, 1, 1, 1) (1, 2, 1, 1, 1) (1, 1, 2, 1, 1) (1, 1, 1, 2, 1) (1, 1, 1, 1, 2) (2, 2, 1, 1) (2, 1, 2, 1) (2, 1, 1, 2) (1, 2, 2, 1) (1, 2, 1, 2) (1, 1, 2, 2) (2, 2, 2)
=> 피보나치네 이거

class Solution {
  public long solution(int n) {
      if (n == 1) return 1;
      if (n == 2) return 2;
		
     return (solution(n-1) + solution(n-2) ) % 1234567;
  }
}

정확성 : 37.5 / 1-6 통과, 나머지 시간초과
재귀함수라서 시간이 오래걸려 시간초과 뜸..
피보나치를 비재귀방식으로 풀어야겠다..!

---

· 완성 코드 1

import java.math.BigInteger;

class Solution {
  public long solution(int n) {
       BigInteger num1 = new BigInteger("1");
       BigInteger num2 = new BigInteger("1");
       BigInteger answer = new BigInteger("0");
       BigInteger divide = new BigInteger("1234567");
       if (n == 1)
       	return 1;

       for (int i = 1; i < n; i++) {
       	answer = num1.add(num2);
       	num1 = num2;
       	num2 = answer;
       }

       return answer.mod(divide).longValue();
  }
}

long 타입도 범위가 초과되어서 BigInteger 이용해서 해결했음...!

 

---

· 완성 코드 2

class Solution {
  public long solution(int n) {
       long num1 = 1;
       long num2 = 1;
       long answer = 0;
       if (n == 1)
	       return 1;

       for (int i = 1; i < n; i++) {
	       answer = (num1 + num2) % 1234567;
	       num1 = num2;
	       num2 = answer;
       }
       
       return answer;
  }
}

어차피 1234567을 계속 나눠야되기 때문에 위의 방법보다 이렇게 푸는게 보기에 훨씬 깔끔하다..!!!

 

---

· 문제 출처

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

알고리즘 연습 - 멀리 뛰기 | 프로그래머스