백준 9184번 c++ 풀이

안녕하세요 오늘은 동적 계획법(다이나믹 프로그래밍)을 이용한 문제를 풀어보겠습니다. 

역시 동적계획법 문제는 점화식이 많은 것 같습니다. 이 문제는 w(a, b, c)인 변수가 3개가 필요한 함수이므로 피보나치 풀이와는 다르게 '3'차원 배열을 만들어서 풀겠습니다.

 

전략:

1. 3차원 배열 arr를 각각 101의 크기로 선언한다.(주어진 범위가 -50~50이기 때문)

2. int w(int a, int b, int c) 함수를 선언한다. 이 함수는 처음 하는 행동이 x = a+50, y = b+ 50, z = c+50을 해준 다음, 만약 arr[x][y][z]가 있으면 계산 할 필요 없이 바로 return해준다. 이부분이 동적 계획법이라고 할 수 있는 부분일 것이다.

3.그 외에는 문제에서 주어진 함수와 똑같이 쓰면 되는데 대신, return하는 값을 3차원 arr에 대입해주고 return 해준다.

4. while문을 만들어, -1 -1 -1이 들어올때 까지 코드를 반복시키게 한다.

 

코드:

#include <bits/stdc++.h>
#include <vector>
using namespace std;
int arr[101][101][101];
int w(int a, int b, int c){
	int x= a+50, y =b+50, z =c+50;
	if(arr[x][y][z]){
		return arr[x][y][z];
	}
	
	if(a<=0 or b<=0 or c<=0){
		return 1;
	}
	else if(a>20 or b>20 or c> 20){
		return w(20, 20, 20);
	}
	else if(a<b and b<c){
		arr[x][y][z] = w(a, b, c-1) + w(a, b-1, c-1)- w(a, b-1, c);
		return arr[x][y][z];
	}
	else{
		arr[x][y][z] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);

		return arr[x][y][z];
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int a, b, c;
	while(1){
		cin>>a>>b>>c;
		if(a==-1 and b==-1 and c==-1){
			break;
		}
		printf("w(%d, %d, %d) = %d\n", a, b, c, w(a,b,c));
	}
}