[백준 17069] 파이프 옮기기 2 C++ (Bottom-up 방식)

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

17069번: 파이프 옮기기 2

 

이번에는 앞에서 포스트 올린 다이나믹 Top-down방식이 아닌,

Bottom-up 방식으로 다이나믹 문제를 풀어보겠습니다.

 

Top-down은 아래 링크를 참고 하시면 됩니다.

https://rolypolytoy.tistory.com/17

[백준 17069] 파이프 옮기기 2 C++ (Top-down 방식)

 

 

다이나믹에는

Top-down방식과 Bottom-up 방식이 있습니다.

1. Top-down 방식 

큰문제를 작은문제로 나누고, 작은문제를 풀고 큰문제를 푸는 순으로 갑니다.

재귀 호출을 이용하는 푸는 방식을 Top-down 방식이라고 합니다.

 

2. Bottom-up 방식

문제를 크기가 작은 문제부터 차례대로 풀고, 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푸는 방식.

그래서, 작은 문제를 풀면서 왔기 때문에, 큰 문제를 항상 풀 수 있어야 합니다. 이런 매커니즘을 계속 반복하여 가장 큰 문제를 풀 수 있어야 합니다. 

 

이번에는 Botton-up 방식으로

재귀를 사용하지 않고 차례로 풀면서 문제의 크기를 조금씩 키워가는 방식으로  '파이프 옮기기 2'를 풀어볼려고 합니다.

이전의 포스트는 재귀로 통하여 N, N까지 간다음에, 다시 return하면서 경우의 수의 누적합을 구했습니다.

 

이번에는 1, 2에서 N, N으로 가면서 누적합을 구하는 Bottom-up방식을 사용해보겠습니다.

 

 

1, 1 좌표부터 시작하여 초기화 된 d[1][2][0] 에 시작값을 대입하고 N, N까지 진행하면서 모든 경우의 수를 가면서 더했습니다. 이 경우, O(N^2)의 시간복잡도가 나오기 때문에, 32^32 = 1024정도 계산밖에 하지 않습니다.

 

 

다이나믹의 Top-down 방식과 Bottom-up 방식의 경우 결과는 같지만, 푸는 방식에서 차이가 약간식 있습니다.

 

 

요약하자면,

Top-down의 경우 재귀 함수를 호출하여 마지막 원하는 케이스에 도달했을 때 return 하면서 값을 구하는 방식이고,

Bottom-up의 경우, 목적지까지 도달하기 위해, 도달하는 과정에 모든 경우의 수를 구해 누적합을 구하는 과정입니다.

 

전체 코드는 다음과 같습니다.

 

#include <iostream>
#include <cstring>

using namespace std;

#define input_max 32 + 1  //입력의 최대값
#define dir_max 3
int n;

int a[input_max][input_max];

long long d[input_max][input_max][dir_max];  //DP 배열 선언


void solution() {

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> a[i + 1][j + 1];
		}

	d[1][2][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {

			if (!a[i][j + 1]) d[i][j + 1][0] += d[i][j][0] + d[i][j][2];
			if (!a[i + 1][j]) d[i + 1][j][1] += d[i][j][1] + d[i][j][2];
			if (!a[i + 1][j + 1] && !a[i + 1][j] && !a[i][j + 1]) d[i + 1][j + 1][2] += d[i][j][0] + d[i][j][1] + d[i][j][2];


		}
		



	long long result = d[n][n][0] + d[n][n][1] + d[n][n][2];

	cout << result << '\n';

}
int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	solution();


	return 0;
}