반응형
문제 링크
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하면 됩니다.
제한사항
- n은 1 이상, 2000 이하인 정수입니다.
입출력 예
n | result |
4 | 5 |
3 | 3 |
입출력 예 설명
입출력 예 #1
위에서 설명한 내용과 같습니다.
입출력 예 #2
(2칸, 1칸)(1칸, 2칸)(1칸, 1칸, 1칸)총 3가지 방법으로 멀리 뛸 수 있습니다.
코드
class Solution {
public long solution(int n) {
// 길이가 2001인 dp 배열 선언
int[] dp = new int[2001];
dp[1] = 1; // n이 1일 때 방법의 수
dp[2] = 2; // n이 2일 때 방법의 수
// i = 3부터 dp 길이까지 반복
for (int i = 3; i < dp.length; i++) {
// i - 2일 때 방법의 수 + i - 1일 때 방법의 수를 저장
dp[i] = (dp[i - 2] + dp[i - 1]) % 1234567;
}
return dp[n];
}
}
코드 설명
주석 참고
- 이 문제는 멀리뛰기하는 방법의 수를 계산하는 문제다. 다이나믹 프로그래밍(DP)을 활용하여 시작점에서 주어진 n까지 멀리뛰기를 하는 방법의 수를 찾을 수 있다.
- n은 2000 이하이기 때문에 배열의 크기가 2001인 dp 배열을 초기화한다.
- dp[1]과 dp[2]에 n이 1일 때와 2일 때 멀리뛰기를 하는 방법의 수를 초기화한다. (1일 때는 1, 2일 때는 2가지 방법으로 멀리 뛰기를 할 수 있다.)
- for 문을 통해 i가 3부터 dp 배열의 길이까지 반복하여 (dp[i - 2] + dp[i - 1]) 합하여 dp[i]에 저장한다.
- 문제에서 1234567을 나눈 나머지를 리턴하라는 요구가 있으므로 위 연산에 % 1234567을 계산한다.
- 반복문을 마친 후 dp[n]을 반환한다. (dp[n]에 n까지 멀리뛰기를 하는 방법의 수가 저장된다.)
반응형
'코딩 테스트(Coding Test) > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 괄호 회전하기 - 자바(Java) (0) | 2023.08.28 |
---|---|
[프로그래머스] 귤 고르기 - 자바(Java) (0) | 2023.08.27 |
[프로그래머스] N개의 최소공배수 - 자바(Java) (0) | 2023.08.25 |
[프로그래머스] 예상 대진표 - 자바(Java) (0) | 2023.08.24 |
[프로그래머스] 점프와 순간 이동 - 자바(Java) (0) | 2023.08.23 |