티스토리 뷰
스터디 1차시에서 진행 했던 내용은 다이나믹 프로그래밍이다. 어려웠다. 그래서 다시 공부했다.
주비 누나가 주신 링크 (https://youtu.be/0o2hF-To_6Q) 로 복습을 했다. 참 어려웠다.
연습문제도 풀었다. 아래 두 문제는 복습 겸 풀었던 연습문제다.
연습 문제 01 - 2747번 : 피보나치 수
#include< iostream >
using namespace std;
long long int memo[46];
//Top-Down
//long long int fibonacci(int n) {
// memo[1] = 1;
// memo[2] = 1;
// for (int i = 3; i <= n; i++) {
// memo[i] = memo[i - 1] + memo[i - 2];
// }
// return memo[n];
//}
//Bottom-Up
long long int fibonacci(int n) {
if (n <= 1) return n;
else {
if (memo[n]>0) {
return memo[n];
}
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}
}
int main(void) {
int N;
cin >> N;
cout << fibonacci(N) << endl;
return 0;
}연습 문제 02 - 1463번 : 1로 만들기
#include< iostream >
using namespace std;
long long int D[1000001];
long long int memo(int n) {
D[1] = 0;
for (int i = 2; i <= n; i++) {
D[i] = D[i - 1] + 1;
if (i % 2 == 0 && D[i] > D[i/2] +1) {
D[i] = D[i / 2] + 1;
}
if (i % 3 == 0 && D[i] > D[i / 3] + 1) {
D[i] = D[i / 3] + 1;
}
}
return D[n];
}
int main() {
int N;
cin >> N;
if (N >=1 && N <=1000000) {
cout << memo(N) << endl;
}
return 0;
}
(위의 두 문제는 개인적으로 따로 푼 연습문제니까 설명은 안올릴게요)
(이제 진짜 과제 풀이!)
과제 01 - 9095번 : 1,2,3 더하기
첫 과제 문제다. 다이나믹 프로그래밍이 익숙하지 않아서 접근하기 어려웠었다. 사실 위의 링크를 걸어둔 백준 강의에서 힌트를 얻고 푼 문제이다. 참 재밌었다.
#include< iostream >
using namespace std;
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int DP[11] = {};
int k;
DP[0] = 1;
cin >> k;
for (int i = 1; i <= k; i++) {
if (i - 1 >= 0) {
DP[i] += DP[i - 1];
}
if (i - 2 >= 0) {
DP[i] += DP[i - 2];
}
if (i - 3 >= 0) {
DP[i] += DP[i - 3];
}
}
cout << DP[k] << endl;
}
return 0;
}
이 문제는 1,2,3 들의 덧셈으로만 정수를 완성할 수있는 갯수를 푸는 문제이다. 이 문제는 간단하게 생각할 수 있다.
1,2,3 각각의 수를 계산하고자하는 정수에서 빼면 나오는 수를 x라고 했을 때, 우리는 x를 표현하기 위한 가짓수를 미리 알고있다면 이 문제의 답을 쉽게 구할 수 있다.
예를 들어, 4를 만들기 위해서는,
1) 1+3 (앞에오는 수가 1인 경우)
2) 2+2 (앞에오는 수가 2인 경우)
3) 3+1 (앞에오는 수가 3인 경우)
이렇게 3종류가 나온다.
3을 구하기 위한 가짓수는 1+1+1 / 2+1 / 1+2 / 3 으로 총 4가지. (DP[3]에 이미 저장되어있을것)
2를 구하기 위한 가짓수는 1+1 / 2 로 총 2가지. (DP[2]에 이미 저장되어있을것)
1을 구하기 위한 가짓수는 1 로 총 1가지. (DP[1]에 이미 저장되어있을것)
3가지를 모두 더하면 정답인 7가지가 나온다.
처음 틀렸던 이유는 메모이제이션을 위한 배열의 크기의 조절실패... 였다. 다음 부턴 꼭 실수하지 않아야겠다.