BOJ/12852

1로 만들기 2

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <algorithm>

int arr[1000001] = { 0, };

int main() {

	int x;
	scanf("%d", &x);

	arr[1] = 0;
	arr[2] = 1;
	arr[3] = 1;

	for (int i = 4; i <= x; i++) {
		if (i % 3 == 0 && i % 2 == 0) {
			arr[i] = std::min({ arr[i - 1],arr[i / 2],arr[i / 3] }) + 1;
		}
		else if (i % 3 != 0 && i % 2 == 0) {
			arr[i] = std::min({ arr[i - 1],arr[i / 2] }) + 1;
		}
		else if (i % 3 == 0 && i % 2 != 0) {
			arr[i] = std::min({ arr[i - 1],arr[i / 3] }) + 1;
		}
		else {
			arr[i] = arr[i - 1] + 1;
		}
	}
	printf("%d\n", arr[x]);
    
    ///여기까지만 사용하면 1463문제///
    
    
	printf("%d ", x);

	while (1) {
		if (x == 1) {
			break;
		}
		if (x % 3 == 0 && x % 2 == 0) {
			if (arr[x - 1] == std::min({ arr[x - 1],arr[x / 2],arr[x / 3] })) {
				printf("%d ", x - 1);
				x = x - 1;
			}
			else if (arr[x/2] == std::min({ arr[x - 1],arr[x / 2],arr[x / 3] })) {
				printf("%d ", x/2);
				x = x / 2;
			}
			else if (arr[x/3] == std::min({ arr[x - 1],arr[x / 2],arr[x / 3] })) {
				printf("%d ", x/3);
				x = x / 3;
			}
		}
		else if (x % 3 != 0 && x % 2 == 0) {
			if (arr[x - 1] == std::min({ arr[x - 1],arr[x / 2] })) {
				printf("%d ", x - 1);
				x = x - 1;
			}
			else if (arr[x / 2] == std::min({ arr[x - 1],arr[x / 2] })) {
				printf("%d ", x / 2);
				x = x / 2;
			}
		}
		else if (x % 3 == 0 && x % 2 != 0) {
			if (arr[x - 1] == std::min({ arr[x - 1],arr[x / 3] })) {
				printf("%d ", x - 1);
				x = x - 1;
			}
			else if (arr[x / 3] == std::min({ arr[x - 1],arr[x / 3] })) {
				printf("%d ", x / 3);
				x = x / 3;
			}
		}
		else {
			printf("%d ", x - 1);
			x = x - 1;
		}

		if (x == 1) {
			break;
		}
	}
}

1로 만들기(1463)의 응용 문제이다.

1463번에서 만든 최소 계산 수 배열을 통해 최소 계산을 해나가는 과정을 출력한다.

1이 입력되는 경우를 생각하지 않으면 출력초과 발생(무한loop)