소요시간
5분 걸렸다. 사실 이 문제는 한 2달 전쯤 백준에서 똑같은 문제를 풀었었기 때문에 금방 풀 수 있었다.
사용한 자료구조 및 알고리즘
DP를 사용했다. 메모이제이션으로 그 값을 1부터 60000까지 기록했고, 최종적으로 return하는 값은 dp[n]이 될 것이다. 점화식을 잘 유도해 낼 수 있어야 한다. DP 유형의 문제는 많이 풀어볼수록 익숙해진다. 나도 이제 다른 문제 유형을 볼때 아.. 이런 DP인데 ? 라는 느낌까지는 온다. 하지만 어떻게 , 어디서 메모이제이션을 해줘야할지 몰라서 헤매는 경우가 많다.
풀이방법
우선 쭉 그려보다보면 규칙을 알 수 있다.
n이 1일 때 => 나올 수 있는 경우의 수는 1개
n이 2일 때 => 나올 수 있는 경우의 수는 2개
n이 3일 때 => 나올 수 있는 경우의 수는 3개
n이 4일 때 => 나올 수 있는 경우의 수는 5개
n이 5일 때 => 나올 수 있는 경우의 수는 8개
...(반복)
여기서 우리는 규칙을 발견할 수 있는데
바로 dp[i] = dp[i-1] + dp[i-2] 라는 것이다.
즉, dp[3] = dp[2] +dp [1],
dp[4] = dp[3] + dp[2] ...
...
dp[60000] = dp[59999] + dp[59998] 이 될 것이다.
한 가지 주의할 점은 이 경우 값이 엄청나게 커지기 때문에 문제에서 제시한대로 한 번 기록될 때마다 1,000,000,007 로 나누는 작업이 필요하다.
소요시간은 배열의 반복문이 60000 번 반복하므로, m이 60000이라고 하면 O(m) 이 걸릴 것이다.
아주 짧은 시간이다.
소스코드
class Solution {
public int solution(int n) {
int dp[]=new int[60001];
dp[1]=1;
dp[2]=2;
int mod=1000000007;
for(int i=3;i<dp.length;i++){
dp[i]=(dp[i-1]+dp[i-2])%mod;
}
return dp[n];
}
}회고
현재 내가 스스로 생각하기에 기본적인 알고리즘들 ( DP, 그래프이론, 이분탐색, 완전탐색, 그리디알고리즘 등등..) 중에서 가장 부족하다고 생각하는게 DP와 그리디알고리즘이다. DP 문제를 많이 풀어봐야겠다고 느끼고 있다. 반면 가장 잘한다고 생각하는 건 그래프 이론과 BFS, DFS 인데 이 유형은 이제 잠시 놓고 다른 유형도 풀어봐야겠다고 생각하고 있다.
하루에 백준 1문제 이상 푸는 것을 목표로 하고 있다.
https://solved.ac/profile/anwlro0212
