[프로그래머스][Lv.2] - 멀리뛰기

 

● 소감

- 어려워보였지만 어렵지 않았다.

 

● 나의 풀이

1) 문제 이해

 

- 처음 문제를 접했을 때 음~ 어떻게 풀지~ 했지만, 몇 개를 직접 만들어봤을 때 피보나치 수열이었다는 걸 알게 되었다. 코테에서 피보나치가 나왔다? 그럼 바로 다이나믹 프로그래밍으로 간다.

 

2) 조건 찾기

 

- 여느 피보나치 수열이 그렇듯 1, 2번째의 가정은 바로 도출하고, 그 이후론 계산을 하는 방식으로 간다.

- n - 2 만큼의 for문을 돌려서 결과에 접근한다.

 

3) 나머지를 구하라?

 

- 이런 문제의 경우 나머지를 구하라는 문제가 많은데 혹시 (a + b) % n 의 방식으로 나머지를 구하려고 하면 백방 틀린다. 처음에는 나머지를 어떻게 구하는지 오히려 헷갈렸지만, 지금은 공식처럼 외우고 있는 식이 있다.

 

(a % n + b % n) % n

 

구한 a의 나머지와 b의 나머지를 더하고 다시 그의 나머지를 구하면 된다.

 

● 내가 작성한 답

long long solution(int n)
{
	long long answer = 0;

	if (n == 1)
		return 1;

	if (n == 2)
		return 2;

	int a = 1;
	int b = 2;

	for(int i = 0; i < n-2; i++)
	{
		answer = (a % 1234567 + b % 1234567) % 1234567;
		a = b % 1234567;
		b = answer;
	}

	return answer;
}