반응형
728x170
DP의 개념이 있고
Memoization의 개념이 있어야 한다.
https://programmers.co.kr/learn/courses/30/lessons/12945?language=cpp
#배운 점
Memoization과
하위 문제로 나눌 수 있는지 DP 풀이
계산된 결과를 저장하고 바로 불러올 수 있는가?
# 맞는 풀이
#include <string>
#include <vector>
using namespace std;
/*
//재귀로 구현한 피보나치 (memoization x)
int func(int n){
if(n == 0)return 0;
if(n == 1) return 1;
return (func(n-1) + func(n-2)) % 1234567;
}
*/
//for memoization
int arr[100001] = {0};
//해당 배열에 값이 저장 안되어있으면 계산해서 저장하고
//해당 배열에 값이 저장 되어있으면 바로 꺼낸다.
int func(int n){
if(n == 0) return arr[0]; // 기본 - 1
if(n == 1){ // 기본 - 2
if(arr[1] == 0){
arr[1] = 1;
}
return arr[1];
}
//n번째 배열이 비어있다면
if(arr[n] == 0){
//이전의 결과에서 계산해서 저장함.
arr[n] = (func(n-1) + func(n-2))%1234567;
return arr[n];
}else{
//이미 계산되어있다면 바로 불러냄.
return arr[n];
}
}
int solution(int n) {
int answer = 0;
answer = func(n);
return answer;
}
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
프로그래머스, 다음 큰 숫자 : C++ [CPP] (0) | 2021.11.11 |
---|---|
프로그래머스, 땅따먹기 : C++ [CPP] (0) | 2021.11.11 |
프로그래머스, N개의 최소공배수 : C++ [CPP] (0) | 2021.11.10 |
프로그래머스, 두 개 뽑아서 더하기 : C++ [CPP] (0) | 2021.11.10 |
프로그래머스, 예산 : C++ [CPP] (0) | 2021.11.10 |