[백준] 1463 - 1로 만들기

문제

1463번: 1로 만들기

해결 과정

단계별로 풀어보기 중 동적 계획법(Dynamic Programming)에 나온 문제라서 우선 동적 계획법을 시도했다. 당시에는 구하고자 하는 수에서 부터 1로 계산해가는 방식을 사용하려고 했는데 구현 과정에서 막혔다.

BFS를 이용해서 처음 n에 도달하면 탐색을 종료하는 방법을 떠올리고 시도해 보았지만 BFS를 구현한 적이 없어서 실력 부족으로 역시 실패했다.

결국 생각을 바꿔 동적 계획법으로 1부터 n까지 계산해가며 쌓아올리는 방식으로 구현해냈다. 아래는 성공한 결과물이다.

#include <stdio.h>
inline int min(int a, int b) {return a < b ? a : b;}

int main() {
    int n, *dp;
    scanf("%d", &n);
    dp = new int[n+1];
    
    for(int i = 2; i <= n; i ++) {
        if (i%3 == 0) {
            dp[i] = min(dp[i/3], dp[i-1]) + 1;
            if (i%2 == 0)
                dp[i] = min(dp[i] - 1, dp[i/2]) + 1;
        } else if (i%2 == 0) {
            dp[i] = min(dp[i-1], dp[i/2]) + 1;
        } else
            dp[i] = dp[i-1] + 1;
    }
    
    printf("%d\n", dp[n]);
    
}

결과

메모리를 꽤 많이 차지했다.

결과는 살짝 아쉬웠다.

실행 시간은 만족스러운 정도였지만 배열의 크기가 최대 1000000를 차지하는 만큼 메모리를 많이 소모했다.

회고

이후 다른 코드를 보던 중 엄청 기발한 코드를 발견했다.

메모리도 덜 차지하고 실행 시간도 0ms이다.

#include <stdio.h>

int func(int n)
{
	int a, b;
	if (n < 2)
		return 0;
	a = func(n / 2) + n % 2 + 1;
	b = func(n / 3) + n % 3 + 1;
	if (a < b)
		return a;
	else
		return b;
}

int main(void)
{
	int n;

	scanf("%d", &n);
	
	printf("%d\n", func(n));

	return 0;
}

핵심은 a와 b에 값을 할당하는 부분이다. 나누어 떨어지는 지의 여부 확인과 -1 연산을 분리시키는 연산을 통합해 나머지를 더하는 연산으로 바꿨다. 이럴 경우 n이 2나 3씩 나누어지는 만큼 함수의 호출이 줄고 조건 연산도 적어지기 때문에 실행 시간을 획기적으로 줄인다.

다만 현재 연습하고 있는 동적 계획법을 사용한 방법은 아니기 때문에 이런 창의적인 방법이 있다는 것 정도로 알아두면 될 것 같다.