NORMAL2 새로운 방

입력 조건

출력 조건

입력	출력
1 3 3 2 3 2 3 2 3 2 3	Case #1 2

뒤에서 연속된 0의 최대 개수일때 열린다고 했으므로 고등학교 시절 뒤에 0이 최대로 오는 문제와 같이 생각해보면 된다.

각 경비를 곱한다고 했으므로 각 경비를 소인수 분해하여 2의 개수와 3의 개수만 저장하고 마지막까지 갔을 때

두개의 페어가 최대값이 되는 경우를 찾으면 된다. 해당 문제에서는 상, 하, 좌, 우로 이동할 수 있다고 나와있지만, 최단거리로 가야된다고 했으므로 실질적으로 이동가능 한 경우는 하, 우 뿐이다.

처음에 고민했던 부분은 최대값이 각 지점까지 왔을 때 최대값과 같은 가 였는 데 이는 간단한 예로 아님을 확인 할 수 있다.

만일 3*3의 미로에서 배열 1,1로 오는 2가지 경우의 수를 예로 들어보자.

하나는 2가 1개 3이 4개인 경우, 나머지 하나는 2가 2개 3이 2개인 경우 인데, 이때 배열 1,1에서의 최대는 2와 3이 2개씩인 후자가 최대값이 2가 된다. 하지만 그 다음 경로에 2가 3 3이 0개가 추가된다면? 전자의 2가 1개 3이 4개인 경우와 더해져서 최대값이 4가 된다.

문제에서 각 방의 경비의 최대값이 1000이라고 했으므로 각 방의 2와 3의 개수는 2^9 = 512, 3^6 = 729이므로 2가 9개 3이 6개가 된다.

따라서 더 낮은 경우의 수인 3을 기준으로 잡고 계산을 하였고, N * N의 정사각형에서 이동하는 방의 개수는 2 * N - 1개가 된다. 따라서 해당 조건에서 3의 최대 개수는 (2 * 100 - 1) * 6 + 1 = 1195개이다 (1을 더한 이유는 하나도 없는 경우를 생각해서)

room[100][100][2]에서 첫번째 인자는 해당 room[i][j]의 경비에서 2의 개수, 두번째 인자는 3의 개수이다.

cost[100][100][1195]라는 배열은 해당 위치 까지 왔을 때 cost[i][j][three] = two 즉 3의 개수(three) 당 2의 개수(two)를 저장했다.

또한 다 계산하기는 수고를 덜기위해 index 배열을 만들어 각 3의 개수가 존재하는지 저장하였다.(예를 들어 해당 경로까지 왔을 때 3의 개수가 5개 2의 개수가 2개였다면, cost[i][j][5] == 1 로 저장, 후에 cost 값이 1인 값만 계산하였다.)

0행과 0열의 경우는 직선으로 오는 방법 밖에 없기 때문에 미리 계산을 하였다.

for문의 시작은 이동 개수를 기준으로 대각선을 계산하였다.

예) k값에 따른 배열

0 1 2 3            

1 2 3

2 3

3

만약에 해당 위치에서 3의 값이 같은 두 경로가 존재하면 비교하여 2의 값이 더 큰 값을 저장하고(max로 계산),

마지막까지 갔을때는 3의 값과 2의 값의 페어의 개수를 구하고(3의 개수와 2의 개수중 작은 값이 페어의 개수, min으로 계산)

그 값들 중 가장 큰 값이 정답이 된다.

소스코드

#include 
#include 
#define max(a, b) (a > b ? a : b);
#define min(a, b) (a > b ? b : a);

int cost[100][100][1195]; //해당 구간에서 3의 개수당 2의 개수
int index[100][100][1195];
int main(void) {

	setbuf(stdout, NULL);
	int room[100][100][2];
	int TC;
	int test_case;
	int N;
	int two, three;
	int num;
	int temp;
	int ans;
	int result;
	int i, j, k, l;
	scanf("%d", &TC);
	for (test_case = 1; test_case <= TC; test_case++) {

		
		
		scanf("%d", &N);
		for (i = 0; i < N; i++){
			for (j = 0; j < N; j++){
				scanf("%d", &num);
				two = three = 0;
				while (num % 2 == 0){
					two++;
					num /= 2;
				}
				while (num % 3 == 0){
					three++;
					num /= 3;
				}
				room[i][j][0] = two;
				room[i][j][1] = three;
			}
		} //해당 값을 입력 받아 소인수분해 하여 2의 개수와 3의개수를 저장한다.


		temp = room[0][0][1]; // temp는 해당 구간에서 3의 개수

		cost[0][0][temp] = room[0][0][0]; // 처음 값을 직접 입력
		index[0][0][temp] = 1;
		for (i = 1; i < N; i++){ //0행 값 입력
			cost[0][i][temp + room[0][i][1]] = cost[0][i - 1][temp] + room[0][i][0];
			index[0][i][temp + room[0][i][1]] = 1;
			temp = temp + room[0][i][1];
		}

		temp = room[0][0][1];
		for (i = 1; i < N; i++){ //0열 값 입력
			cost[i][0][temp + room[i][0][1]] = cost[i - 1][0][temp] + room[i][0][0];
			index[i][0][temp + room[i][0][1]] = 1;
			temp = temp + room[i][0][1];
		}

		for (k = 2; k <= 2 * (N - 1); k++){

			for (i = 1; i < k; i++){
				j = k - i;

				if (i < N && j < N){
					for (l = 0; l <= 6 * k ; l++){
			
						if (index[i][j - 1][l]){ //왼쪽에서 진행하는 경우
							cost[i][j][l + room[i][j][1]] = max(cost[i][j - 1][l] + room[i][j][0], cost[i][j][l + room[i][j][1]]); //왼쪽에서 올때
							index[i][j][l + room[i][j][1]] = 1;

						}
						if (index[i - 1][j][l]){ //위에서 진행하는 경우

							cost[i][j][l + room[i][j][1]] = max(cost[i - 1][j][l] + room[i][j][0], cost[i][j][l + room[i][j][1]]); //위에서 올때
							index[i][j][l + room[i][j][1]] = 1;

						}
					}
				}
			}
		}
		ans = 0;
		result = 0;
		for (i = 0; i < 1195; i++){
			if (index[N - 1][N - 1][i]){

				result = min(cost[N - 1][N - 1][i], i);
				ans = max(result, ans);
			}
			
		}


		printf("Case #%d\n", test_case);
		printf("%d\n", ans);
		for (i = 0; i < N; i++){
			for (j = 0; j < N; j++){
				for (l = 0; l < 1195; l++){
					cost[i][j][l] = 0;
					index[i][j][l] = 0;
				}
			}
		}
	}
	
	


	return 0;
}

더 쉽게 짤 수 있겠지만 멘탈이 나간 관계로....ㅠ