ORTHODOX

전략: 1. 3이상의 N에 대하여 N자리 이친수는 N-1자리 이친수 뒤에 0을 붙이는 것과, N-2자리 이친수 뒤에 01을 붙이는 경우이기 때문에 점화식은 pr(num) = pr(num-1) + pr(num-2)가 된다 코드: #include long long int arr[100]= {0, 1, 1, 2}; long long int pr(int num){ if(arr[num]){ return arr[num]; } arr[num] = pr(num-1) + pr(num-2); return arr[num]; } using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin>>N; cout

안녕하세요 오늘은 동적계획법으로 문제를 풀어보도록 하겠습니다. 코드: #include using namespace std; int result[301] = {0, }; int score[301] = {0, }; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin>>N; for(int i = 1; i>x; score[i] = x; } result[1] = score[1]; result[2] = score[1] + score[2]; result[3] = max(score[1] + score[3], score[2] + score[3]); for(int i= 4; i

안녕하세요 오늘은 동적 계획법(다이나믹 프로그래밍)을 이용한 문제를 풀어보겠습니다. 역시 동적계획법 문제는 점화식이 많은 것 같습니다. 이 문제는 w(a, b, c)인 변수가 3개가 필요한 함수이므로 피보나치 풀이와는 다르게 '3'차원 배열을 만들어서 풀겠습니다. 전략: 1. 3차원 배열 arr를 각각 101의 크기로 선언한다.(주어진 범위가 -50~50이기 때문) 2. int w(int a, int b, int c) 함수를 선언한다. 이 함수는 처음 하는 행동이 x = a+50, y = b+ 50, z = c+50을 해준 다음, 만약 arr[x][y][z]가 있으면 계산 할 필요 없이 바로 return해준다. 이부분이 동적 계획법이라고 할 수 있는 부분일 것이다. 3.그 외에는 문제에서 주어진 함수와 ..