백준 5569 풀이 실패

다이나믹 프로그래밍 방식을 풀어야하는 것은 금방 알 수 있었다.

그래서 n==2부터 차근차근 규칙을 찾아나가며 점화식을 만들어 코드를 작성했지만 풀이에 실패했다. 우선 다른 문제를 풀며 실력을 키워 다시 도전해야겠다.

실패한 코드를 남기기 위해 작성한다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;

int t;
int n;
int m;
int arr[101][101];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	arr[2][2] = 0;
	for (int i = 2; i < 101; i++) {
		arr[i][2] = 2 % 100000;
		arr[2][i] = 2 % 100000;
	}

	for (int i = 3; i < 101; i++) {
		//arr[i][i] = ((int)pow(2, (i - 1))) % 100000;
		arr[i][i] = arr[i - 1][i - 1] * 2 % 100000;
	}
	
	for (int i = 4; i < 101; i++) {
		arr[3][i] = arr[3][i - 1] + 1 % 100000;
		arr[i][3] = arr[i-1][3] + 1 % 100000;
	}

	for (int i = 4; i < 101; i++) {
		for (int j = 5; j < 101; j++) {
			arr[i][j] = arr[i][j-1] + arr[i - 1][j-1] % 100000;
			arr[j][i] = arr[i][j] % 100000;
		}
	}


	cout << arr[n][m] << '\n';
	return 0;
}