https://school.programmers.co.kr/learn/courses/30/lessons/12945
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
class Solution {
public int solution(int n) {
int[] dpArr = new int[n+1];
dpArr[0]=0;
dpArr[1]=1;
for(int i=2; i<=n; i++){
dpArr[i] = (dpArr[i-1] + dpArr[i-2]) %1234567;
}
return dpArr[n];
}
}
DP 에 대해 공부할 수 있었던 문제였다.
대표적인 DP 문제가 피보나치 였고 공부를 하며 풀이법을 봤는데 그대로 문제를 풀었다.
특이한 점은 1234567 로 나누는 이유였는데, '질문하기'에서 어떤 분이 이유를 적어주셨다.
데이터 타입에 따라 표현할 수 있는 수의 범위가 정해지는데 피보나치는 44번째부터 int 형의 범위를 뛰어넘는다고 한다.
따라서 1234567로 나눈 나머지 값으로 다룸으로써 int 형에서 정상적으로 동작할 수 있도록 하기 위해이다.
다른 DP 문제도 풀어봐야겠다.
'알고리즘 > 문제' 카테고리의 다른 글
| [프로그래머스] Lv2 영어 끝말잇기 / JAVA (0) | 2023.02.26 |
|---|---|
| [프로그래머스] Lv2 다음 큰 숫자 / JAVA (0) | 2023.02.25 |
| [프로그래머스] Lv2 숫자의 표현 / JAVA (1) | 2023.02.23 |
| [프로그래머스] lv2 이진변환 반복하기 / JAVA (0) | 2023.02.22 |
| [프로그래머스] Lv2 올바른 괄호 / JAVA (0) | 2023.02.21 |
