1차원 유형

키워드

1차원 유형의 문제는 점화식이 확실하게 결정되어 있기 때문에 점화식만 구해낸다면 쉽게 문제를 풀어낼 수 있다.

알고리즘

1. 마지막에 값이 올때의 독립된 경우를 구한다.
2. 점화식을 구한다.
3. 초기화를 한다.

문제

1003 피보나치함수

그냥 풀면 시간 없는 문제

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <functional>
#define ll long long
#define len 2001
using namespace std;

int d[len] = {0};

int fibo(int n) {
	if (n <= 1) {
		return d[n];
	}else if (d[n]) return d[n];

	return d[n]=fibo(n - 1) + fibo(n - 2);
}

int main(void) {
	freopen("input.txt", "r", stdin);

	int t;
	cin >> t;

	d[0] = 1;
	d[1] = 1;
	while (t--) {
		int n;
		cin >> n;

		if (n == 0) cout << "1 0" << '\\\\n';
		else if (n == 1) cout << "0 1" << '\\\\n';
		else {
			fibo(n);

			cout << d[n - 2] << ' ' << d[n - 1] << '\\\\n';
		}
	}
}

9461 파도반 수업

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#define ll long long
#define len 1001
using namespace std;

ll d[100];
int main(void) {
	freopen("input.txt", "r", stdin);

	int t;
	cin >> t;

	d[1] = d[2] = d[3] = 1;
	for (int i = 4; i <= 100; ++i) {
		d[i] = d[i - 2] + d[i - 3];
	}

	while (t--) {
		int n;
		cin >> n;
		cout << d[n] << '\\\\n';
	}
}

1차원 - 백트래킹

키워드

문제 처리 과정에서 나온 것을 출력하라는 게 추가로 요구된다. 보통 쉬운문제에다가 이거 하나 붙이면 어려워진다.

그냥 백트래킹 할 줄 알면 쉽게 풀린다.

문제

12852 1로 만들기 2