# 정육면체

# 문제

# 입력 및 출력

# 풀이

뭔가 간단해보이는데 어려웠다.

규칙을 좀 찾으려고 하나하나 풀어보다가 발견했다.

처음엔 점화식을 아래와 같이 잡았다.

min({ dp[x / 2][y][z] + dp[x / 2 + x % 2][y][z], dp[x][y / 2][z] + dp[x][y / 2 + y % 2][z],
dp[x][y][z / 2] + dp[x][y][z / 2 + z % 2] })

이렇게 잡은 이유는 size를 5로 놓고 계산했을 때 1, 4의 합이나 2, 3의 합이 같았기 때문에 그냥 접근하기 쉬우려고 절반을 사용했다.

이렇게 하니까 문제가 하나 발생했다.

(2,2,5) 값을 구할 때를 예를 들어보자.

(2,2,2) 와 같은 케이스는 =(1,1,1) 이라 (2,1,2) + (2,1,2) 한 값보다 작은 1의 값을 갖게 된다.

따라서 (2,2,5) 를 구할 때 (2,2,3) + (2,2,2) != (2,2,1) + (2,2,4) 가 되기 때문에

인덱스의 절반을 접근하는 것이 아니라 전부 확인해줘야 했다.

따라서 최소값을 구하기 위해선 아래의 코드처럼 전부 확인해서 최소값을 찾아야 한다.

for (int i = 1; i <= x / 2; i++) {
	result = min(result, dp[i][y][z] + dp[x - i][y][z]);
}
for (int i = 1; i <= y / 2; i++) {
	result = min(result, dp[x][i][z] + dp[x][y - i][z]);
}
for (int i = 1; i <= z / 2; i++) {
	result = min(result, dp[x][y][i] + dp[x][y][z - i]);
}

위 문제가 백준에도 있어서 백준에 먼저 제출해봤다.

백준에 제출해서 맞은 코드

#include <iostream>
#include <algorithm>
#define INF 987654321
#define SIZE 200
using namespace std;

int dp[SIZE + 1][SIZE + 1][SIZE + 1];

void make_dp() {
	int s[3] = { 0, }, check;
	for (int x = 1; x <= SIZE; x++) {
		for (int y = 1; y <= SIZE; y++) {
			for (int z = 1; z <= SIZE; z++) {
				if (dp[x][y][z] == 0) {
					if (x == y && y == z) { // x==y==z인 경우
						dp[x][y][z] = 1;
						continue;
					}
					s[0] = x, s[1] = y, s[2] = z;
					sort(s, s + 3);
					check = 0;
					for (int i = 2; i <= s[0]; i++) { // 최대공약수로 나누는 경우
						if (s[0] % i == 0 && s[1] % i == 0 && s[2] % i == 0) {
							dp[x][y][z] = dp[s[0] / i][s[1] / i][s[2] / i];
							check = 1;
							break;
						}
					}
					if (check) continue;

					int result = INF;
					for (int i = 1; i <= x / 2; i++) {
						result = min(result, dp[i][y][z] + dp[x - i][y][z]);
					}
					for (int i = 1; i <= y / 2; i++) {
						result = min(result, dp[x][i][z] + dp[x][y - i][z]);
					}
					for (int i = 1; i <= z / 2; i++) {
						result = min(result, dp[x][y][i] + dp[x][y][z - i]);
					}
					dp[x][y][z] = dp[x][z][y] = dp[y][x][z] = dp[y][z][x] = dp[z][x][y] = dp[z][y][x] = result;
				}
			}
		}
	}
}

int main() {
	make_dp();
	int T, x, y, z;
	cin >> T;
	while (T--) {
		cin >> x >> y >> z;
		cout << dp[x][y][z] << "\n";
	}
}

이 코드를 파일 입출력으로 바꿔서 espa에 제출하니까 50점 밖에 나오지 않았다...

최소값을 비교하는 부분이 아니라 조건문으로 dp를 채우는 부분이 문제라고 생각했다.

1,1,x 값이 들어왔을 때 테이블이 빈 상태로 있는다는 것을 확인했다.

최소값을 구하는 반복문에서도 채워지지 않는 부분이고 처음에 조건문으로 초기화도 해주지 않았기 때문이다.

그래서 미리 반복문을 돌려서 (i,i,i) = 1인 것과 (1,1,x) 값을 채워주도록 변경하였다.

이렇게 미리 채워놓으니까 굳이 최대공약수로 나누는 부분이 없어도 되길래 지워버렸다.

최종 코드는 아래와 같다.

#include <fstream>
#include <algorithm>
#define INF 987654321
#define SIZE 200
using namespace std;

ifstream fin("cube.inp");
ofstream fout("cube.out");

int dp[SIZE + 1][SIZE + 1][SIZE + 1];

void make_dp() {
	for (int i = 1; i <= SIZE; i++) {
		dp[1][1][i] = dp[1][i][1] = dp[i][1][1] = i;
		dp[i][i][i] = 1;
	}
	for (int x = 1; x <= SIZE; x++) {
		for (int y = 1; y <= SIZE; y++) {
			for (int z = 1; z <= SIZE; z++) {
				if (dp[x][y][z] == 0) {
					int result = INF;
					for (int i = 1; i <= x / 2; i++) {
						result = min(result, dp[i][y][z] + dp[x - i][y][z]);
					}
					for (int i = 1; i <= y / 2; i++) {
						result = min(result, dp[x][i][z] + dp[x][y - i][z]);
					}
					for (int i = 1; i <= z / 2; i++) {
						result = min(result, dp[x][y][i] + dp[x][y][z - i]);
					}
					dp[x][y][z] = dp[x][z][y] = dp[y][x][z] = dp[y][z][x] = dp[z][x][y] = dp[z][y][x] = result;
				}
			}
		}
	}
}

int main() {
	make_dp();
	int T, x, y, z;
	fin >> T;
	while (T--) {
		fin >> x >> y >> z;
		fout << dp[x][y][z] << "\n";
	}
}