![thumbnail](https://blog.kakaocdn.net/dn/dTOmt0/btsCnJ2knNW/TTxpOOnYw6TMBCceKmJzgK/img.png)
안녕하세요. 이번에는 프로그래머스 멀리 뛰기 문제를 풀어보려고 합니다.
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
Problem
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한 번에 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 이하인 정수입니다.
![](https://blog.kakaocdn.net/dn/ViU2K/btsz9AlNpW2/peWjtr4bFmInzOy6Aahlm1/img.png)
Solution
class Solution {
fun solution(n: Int): Long {
var arr = LongArray(2001)
arr[0] = 0
arr[1] = 1
arr[2] = 2
for(i in 3..n) {
arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567
}
return arr[n]
}
}
이번 문제는 DP로 문제를 풀면 쉽게 풀 수 있습니다.
1칸 | 2칸 | 3칸 | 4칸 | 5칸 |
1 | 1 + 1 | 1 + 1 + 1 | 1 + 1 + 1 + 1 | 1 + 1 + 1 + 1 + 1 |
2 | 1 + 2 | 1 + 1 + 2 | 1 + 1 + 1 + 2 | |
2 + 1 | 1 + 2 + 1 | 1 + 1 + 2 + 1 | ||
2 + 1 + 1 | 1 + 2 + 1 + 1 | |||
2 + 2 | 2 + 1 + 1 + 1 | |||
1 + 2 + 2 | ||||
2 + 2 + 1 | ||||
2 + 1 + 2 | ||||
1 | 2 | 3 | 5 | 8 |
이렇게 보면 우리는 dp식을 구할 수 있습니다. dp [n] = dp [n - 1] + dp [n - 2]를 알 수 있습니다. 그래서 우리는 이 공식을 사용해서 코드를 작성하면 됩니다. 이 문제를 보니까 예전에 풀었더 피보나치 수의 문제가 생각나네요. 피보나치가 궁금하신 분은 한번 아래의 링크를 들어가 보면 도움이 될 것 같습니다.
[프로그래머스] 피보나치 수 Kotlin
안녕하세요. 이번에는 프로그래머스 피보나치 수 문제를 풀어보려고 합니다. https://school.programmers.co.kr/learn/courses/30/lessons/12945 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭.
echung93.tistory.com
1. 다른 사람 코드
class Solution {
fun solution(n: Int): Long = getFibonacci(n + 1)
private tailrec fun getFibonacci(currentNumber : Int, acc : Long = 0, prevSum : Long = 1) : Long =
if(currentNumber == 0) acc
else getFibonacci(currentNumber - 1, prevSum, (prevSum + acc) % 1234567)
}
오늘도 다른 사람의 풀이가 궁금해서 공부해보려고 합니다. 위에 말한 것 처럼 이분은 피보나치 수와 비슷하게 문제를 푼 것을 알 수 있습니다. 여기서 tailrec 꼬리 재귀의 모습도 확인할 수 있었습니다. 꼬리 재귀가 궁금하신 분은 아래의 링크를 보고 오시면 좋을 것 같습니다.
[Kotlin] tailrec 꼬리 재귀 함수에 대하여 알아보기
Tailrec(꼬리 재귀)란, 재귀 함수 내부의 재귀 호출에서 반환된 결괏값을 갖고 어떤 추가 연산도 수행하지 않으며 즉시 반환하는 식으로 작성된 재귀 함수를 꼬리 재귀(tail recursion) 함수라 합니다.
echung93.tistory.com
Performance
1. 내가 작성한 코드 | 2. 다른 사람 코드 |
![]() |
![]() |
'프로그래머스 Algorithm' 카테고리의 다른 글
[프로그래머스] 귤 고르기 Kotlin (2) | 2023.12.23 |
---|---|
[프로그래머스] 추억 점수 Kotlin (2) | 2023.12.22 |
[프로그래머스] N개의 최소 공배수 Kotlin (2) | 2023.12.20 |
[프로그래머스] 콜라 문제 Kotlin (2) | 2023.12.19 |
[프로그래머스] 예상 대진표 Kotlin (2) | 2023.12.18 |