1463 : 1로 만들기

네르기·2021년 9월 6일

동적 프로그래밍 생각 재귀

알고리즘

목록 보기

49/76

어떤 문제인가?

규칙을 찾아 점화식을 만드는 문제.

시행착오 횟수

한 번에 성공.

관찰

숫자 간 관계가 존재한다. 자세한 내용은 후술한다.

1차 시도 : AC

$f(n)$ 을 $n$ 을 1로 만들기 위해 필요한 최소한의 연산 수라고 정의한다.

$N=1$ 일때를 생각하자. 어떠한 연산도 하지 않는다. 따라서 $f(1)=0$ 이다.

$N=2$ 일때를 생각하자.
2로 나누거나 1을 빼서 1을 만들 수 있다. 즉 $f(2)=1$ 이다.

$N=3$ 일때를 생각하자.
1. 3으로 나누거나
2. 1을 뺀 후 2로 나누거나
3. 1을 뺀 후 다시 1을 빼거나

총 3가지 방법이 있다. 최솟값은 $f(3)=1$ 이다.
굵게 강조한 부분은 $n=2$ 일때와 겹치는 부분이다. 그래프를 그려보면 그 관계를 단박에 확인할 수 있다.

일반화하면 다음과 같다.

f(n) = \begin{cases} 0 & (n=1) \\ f(n-1)+1 & (n\geq 2) \end{cases}

이때, 1번과 2번 연산에 의해 다음과 같은 관계식이 주어진다.

f(n) = \begin{cases} min(f(n-1)+1,\;f(\frac{n}{2})+1) & (n \equiv 0\;(\mod 2)) \\ min(f(n-1)+1,\;f(\frac{n}{3})+1) & (n \equiv 0\;(\mod 3)) \end{cases}

이를 코드로 나타내면 다음과 같다.

#include <stdio.h>
#define MIN(x,y) x<y?x:y

int P[1000001];

int main()
{
	int N,i;
	scanf("%d",&N);
	for(i=2;i<=N;i++) {
        P[i]=P[i-1]+1;
        if(i%2==0) P[i]=MIN(P[i], P[i/2]+1);
        if(i%3==0) P[i]=MIN(P[i], P[i/3]+1);
	}
	printf("%d",P[N]);
}

다른 분들의 풀이

이 문제는 재귀함수로도 풀 수 있다.

#include <stdio.h>
int N;
int c(int X){
    int a,b;
    if(X<2)return 0;
    a=c(X/2)+X%2+1;
    b=c(X/3)+X%3+1;
    return a<b ? a : b;
}
int main(){
    scanf("%d",&N);
    printf("%d",c(N));
}