백준: 1463번 - 1로 만들기

1. 문제 요약

정수 X에 적용할 수 있는 연산은 세가지 인데

1. 3의 배수이면 3으로 나누기

2. 2의 배수이면 2로 나누기

3. 1을 빼기

 

X를 1로 만들 수 있는 최소한의 연산 횟수를 구하는 것이 목표

 

2. 첫번째 풀이

처음부터 최소 값을 구할 수 있는 방법이 없을까 부터 생각해봤다

어떻게 10을 입력했는데 2를 먼저 나누지 않고 1을 먼저 뺐을까?

그래서 X-1의 값이 3의 배수라면 빼고 3으로 나누는 것이 그냥 2를 나눴을 때 보다

연산횟수가 더 작아진다는 것을 알게 되었다

 

그래서 반복문 안에서 조건문을 사용해서

3의 배수인지 판단하기 - 1을 뺐을 때 3의 배수가 되는지 판단하기 - 2의 배수인지 판단하기

의 순서로 X를 판단하게 했고 그 마저도 안된다면 1을 빼도록 했다

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
	int X, cnt = 0;

	scanf("%d", &X);

	while (X != 1) {
		if (X % 3 == 0) {
			X /= 3;
			//printf("%d\n", X);
			cnt++;
			continue;
		}
		if ((X - 1) % 3 == 0) {
			X--;
			//printf("%d\n", X);
			cnt++;
			continue;
		}
		if (X % 2 == 0) {
			X /= 2;
			//printf("%d\n", X);
			cnt++;
			continue;
		}
		X--;
		//printf("%d\n", X);
	}


	printf("%d\n", cnt);

	return 0;
}

 그런데 다른 예시에서 틀린 부분이 있었던 것 같았다

그리고 직접 풀어보니 연산이 중복되는 부분도있는 것 같았다

 

 3. 두번째 풀이

피보나치 수열을 최적화 했던 것 처럼 메모리 배열을 만들어 놔야 한다

풀이 방법도 Top-down 형식이 아니라 Bottom-up 형식으로 짜야 더 간단한 것 같다

그래서 이렇게 고쳤었다

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
	int X, i = 2;
	int M[1000001] = {0};

	scanf("%d", &X);

	M[1] = 0;

	while (i <= X) {
		if (i % 3 == 0) {
			M[i] = 1 + M[i / 3];
		}
		else if ((i - 1) % 3 == 0) {
			M[i] = 2 + M[(i - 1) / 3];
		}
		else if (i % 2 == 0) {
			M[i] = 1 + M[i / 2];
		}
		i++;
	}

	printf("%d\n", M[X]);
	
	return 0;
}

 

그런데도 틀렸습니다로 나왔다..

그래서 구글링의 힘을 조금 빌렸다

 

3. 세번째 풀이

생각해보니까 이 문제는 최소 값을 한번에 정할 수 없었다

만약에 i가 3의 배수일 경우에 1을 빼면 2의 배수가 된다고 생각해 보자

그럴 경우에 3을 먼저 나눴을 때와 1을 빼고 2를 나눴을 때 중

어느 것이 더 결과 값이 작을 지는 모르는 것이다

다른 경우를 들자면 i가 6의 배수라면 마찬가지로

2로 나눴을 때와 3으로 나눴을 때 어떤 값이 더 작을지 모른

그런데 나는 무조건 3으로 나눈 것이 더 작을 거라고 생각해 왔던 것 같다

그래서 진짜 마지막으로 다시 풀었다

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
	int X;
	int M[1000001] = {0};

	scanf("%d", &X);

	M[1] = 0;

	for (int i = 2; i <= X; i++) {
		M[i] = M[i - 1] + 1;
		if (i % 3 == 0) {
			if (M[i] > M[i / 3] + 1)
				M[i] = M[i / 3] + 1;
		}
		if (i % 2 == 0) {
			if (M[i] > M[i / 2] + 1)
				M[i] = M[i / 2] + 1;
		}
	}

	printf("%d\n", M[X]);
	
	return 0;
}

 

먼저 1을 빼놓고 나머지 두 연산들의 값과 비교하는 것이다

여기서 핵심은 else if 를 쓰지 않는 것 !!

 

이렇게 풀어보고 나니까 코딩테스트 문제들은 변수의 개수를 최소한으로 해야겠다고 깨달았다

변수의 개수가 늘어나면 늘어날 수록 머리를 쓰지 않는 느낌을 받았다