[알고리즘][Swift] #4. 멀리 뛰기

안녕하세요! caution 입니다. '-'

알고리즘 풀이 네 번째 시간입니다. 이번 문제는 지난 번 시간 처럼 '순열과 조합'과 관련된 문제네요. 

정말 고등학교 때 공부한 거 다 잊어버렸나봐요 흑흑.... 덕분에 오랜만에 인강도 들어봤어요 ㅋㅋ

빠르게 풀어볼까요! 

(포스팅 프레임이 매번 달라져서 죄송합니다.. 과도기를 겪고 있어요 ㅋㅋㅋㅋㅋ)

오늘의 문제는 Level 3. 멀리 뛰기 입니다.  

문제 설명  효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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 이하인 정수입니다.

 이 문제를 보고 처음 떠올렸던 건, 왜 1234567 로 나눈 나머지를 리턴하는 걸까? 였습니다. 이 알고리즘을 풀고 계신다면 이 문장에 대해 한 번 고민해보시는 것도 좋을 것 같아요. 제가 했던 많은 시행착오들을 없애줄 수 있기 때문이죠.

 그리고 주의하실점은, 문제 상으로 리턴값의 타입은 Int이지만, 실제로 코드를 실행시키면 리턴타입이 Int64이 아니라는 오류가 뜰겁니다. 그래서 먼저 solution의 return type을 Int 에서 Int64로 변경해주시고, 실제로 반환값도 Int64로 변환해서 리턴해주셔야 합니다.

 풀이 전에 간략하게 문제를 좀 더 살펴보죠. 칸의 개수에 따라 멀리뛰기를 할 수 있는 경우의 수는 얼마일까요? 

칸의 개수	경우의 수	경우
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) (2,1,2) (1,2,2)

 눈에 띄는 규칙성이 보이시나요? 칸이 3개일 때는 칸이 1개인 경우와 칸이 2개인 경우를 합치면 됩니다. 즉 칸이 n개인 멀리뛰기의 경우의 수는 칸이 (n-1)인 경우의 수와 칸이 (n-2)인 경우를 더한 경우가 됩니다. 왜 이렇게 될까요?

 위 그림을 보면 5번째 칸으로 가는 경우를 조금 풀어서 보면, 3번째 칸에서 2칸을 뛰는 경우와, 4번째 칸에서 1칸을 뛰는 경우로 볼 수 있습니다. 그렇기 때문에 칸이 3개일 때의 멀리뛰기 경우의 수와, 칸이 4개일 때 경우의 수를 더하면 칸이 5개일 때 멀리뛰기 경우의 수를 구할 수 있습니다. 이렇게 수를 나열했을 때 n 번째 수는 n-1 번째 수와 n-2 번째 수를 더한 수인 집합을 '피보나치 수열'이라고 합니다. 도와줘요 위키피디아! 

 이제 어떻게 풀어야할 지 대략 감이 잡히시나요?

 바로 풀이 들어갑니다!!!!

문제 해결

---

 저는 피보나치 수열의 방법을 이용해서 문제를 풀었습니다.

1. 첫 번째와 두 번째 경우의 수인 1, 2가 들어있는 result 배열을 선언하고, 이 result배열에 피보나치 수들을 넣어봅시다.

2.  n+2 번째 수를 계산하기 위해서는 n+1과 n을 더해나가야하기 때문에, 계속해서 값이 1씩 증가할 변수 1를 선언하고 0으로 초기화 합니다.

3. 피보나치 배열 result에 n칸만큼의 수가 들어갈 때까지 수를 계속 넣어줍니다.

3-1 수를 넣는 방식은 간단합니다. i=0으로 시작하기 때문에 첫 번째 값(result[i])과 두 번째 값(result[i+1]) 을 더해서 1234567로 나눈 나머지를 넣습니다.

3-2 값을 하나 넣었기 때문에 i에 1을 더해줍니다.

4. result 배열의 count 값이 n과 같아서 while문을 빠져나오면, result[n-1] 값을 (왜냐면 배열은 0번째부터 시작하니까) Int64로 변환해서 리턴해줍니다.

주의사항

3-1 에 1234567의 나머지를 구하는 이유는 수열을 계속해서 만들어나가면 Swift의 Int 범위를 넘어서는 수가 발생할 수 있기 때문에, 런타임 오류가 발생합니다. 그렇기 때문에 수열을 저장하는 것이 아니라, 1234567로 나눈 나머지의 결과값을 저장해야 합니다.

다음은 코드입니다 :)

결과입니다 :)