알고리즘 #11 (DP, 백준 2748번, 9095번) [C++]

백준의 DP문제를 풀어보려고 한다!

먼저 DP가 뭔지 알아봤다.

 

이 게시글에 설명이 잘되어있었다. 

https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP

[자료구조와 알고리즘] 동적 계획법(Dynamic Programming, DP)

 

동적 계획법 DP(Dynamic Programming)란?

문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해 최종 목적에 도달하는 방식의 알고리즘

 

Memoization : 동일한 문제를 반복해야할 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식 (중복 계산 감소)

TOP-DOWN : 문제 풀이가 위 → 아래로 진행

BOTTOM-UP : 문제 풀이가 아래 → 위로 진행 

 

아래 블로그의 초급자!를 위한 백준 DP문제 연습 순서를 따라가 보려고 한다.

 

https://stonejjun.tistory.com/24

좋은 DP 문제들 추천

 

[백준 2748번]

https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>

using namespace std;

long long Npibo(int n) {
	long long Fn[92];
	Fn[0] = 0;
	Fn[1] = 1;
	Fn[2] = 1;

	for (int i = 3; i <= n; i++) {
		Fn[i] = Fn[i - 1] + Fn[i - 2];
	}
	return Fn[n];
}

int main() {
	int n;
	cin >> n;
	cout << Npibo(n);
}

처음 오류가 발생했을 때 뭐가 문젠지 찾아보려고 Fn[n]을 다 출력했다. 자료형 크기 때문에 n이 커지면 쓰레기 값이 출력됐다. int로는 턱없이 부족해 long long을 사용해야되는 것이었다.

 

[백준 9095번]

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int T, n;
	cin >> T;

	int count[12];
	count[1] = 1;
	count[2] = 2;
	count[3] = 4;

	for (int i = 4; i < 12; i++) {
		count[i] = count[i - 1] + count[i - 2] + count[i - 3];
	}
	for (int i = 0; i < T; i++) {
		cin >> n;
		cout << count[n] << endl;
	}
}

문제에서 제한이 정수 n이 11보다 작다고 제시되었기 때문에 위처럼 1~11의 모든 방법의 수를 다 구하는 방식으로 풀 수 있었지만 숫자가 커질 수록 낭비가 클 것 같다. 다른 방법으로 풀어볼 필요도 있을 것 같다. 

 

이 문제도 쉽게 못풀고 검색을 많이 했다. 1, 2, 3의 방법의 수만 구하고 이를 이용해서 나머지 4, 5, ... 의 방법의 수를 구하는 형식의 패턴을 알아낸다는 것은... 아직 너무 어렵다...