[백준/BOJ] 1463번 1로 만들기 (C/C++)

백준 온라인 저지(BOJ) 1463번 1로 만들기

https://www.acmicpc.net/problem/1463

* 사용언어 : C언어, C++

 

1. 문제

정수 X에 가할 수 있는 연산은 3가지(3으로 나누기, 2로 나누기, 1 빼기)

3가지 연산을 활용하여 X를 1로 만들 때 연산을 사용하는 최소값 출력

 

2. 풀이

Dynamic Programming의 Bottom-Up 방식을 활용하여 O(N)의 시간 복잡도로 풀 수 있는 문제입니다.

i번째의 dp 값을 구하는 규칙은 상당히 간단한데, 아래 3개의 값 중 최소값을 골라서 저장하면 됩니다.

1) dp[i / 3] + 1 (i가 3으로 나누어지는 경우)

2) dp[i / 2] + 1 (i가 2로 나누어 지는 경우)

3) dp[i - 1] + 1

 

저는 i == 24까지 dp값을 손으로 직접 계산해본 후 '위 순서대로 최소값이 정해진다'고 착각을 했었는데,

그렇게 오해를 하여 설계를 했더니 오답이 나왔습니다.

 

고민을 하다가 질문 게시판에서 아래 글을 통해 반례를 찾아서 문제를 해결할 수 있었습니다.

https://www.acmicpc.net/board/view/136706

글 읽기 - if가 아니라 elif이면 오답이 뜹니다우ㅜ

 

해당 글에서 확인할 수 있는 반례는 642로, 처음에 2로 나눌 때 총 10번을 연산하여 최소값이 됩니다.

1) 642 → 214 → 107 → 106 → 53 → 52 → 26 → 13 → 12 → 4 → 2 → 1 (11번)
2) 642 → 321 → 320 → 160 → 80 → 40 → 20 → 10 → 9 → 3 → 1 (10번)

 

그 외에도 3과 2로 모두 나눌 수 있는 경우에는 2로 나누는 것이 최소일 수도 있고,

2나 3으로 나눌 수 있어도 1을 빼는 것이 최소일 수도 있다는 것 또한 해당 케이스를 통해 알 수 있었습니다.

 

성급한 일반화의 오류를 범하지 않도록 더 많이 조심해야겠다는 교훈을 얻을 수 있었습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1463_1로 만들기
2008KB	4ms
*/
#include <cstdio>

const int LM = 1e6 + 1;
char dp[LM];
int N;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);

	for (int i = 2; i <= N; ++i) {
		dp[i] = dp[i - 1] + 1;
		if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) dp[i] = dp[i / 3] + 1;
		if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) dp[i] = dp[i / 2] + 1;
	}

	printf("%d\n", dp[N]);
	return 0;
}