[코테]13-1로 만들기

1로 만들기

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
어떤 정수 N에 위와 같은 연산을 선택해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 구하는 문제.

X -> X/3
X -> X/2
X -> X-1
큰 문제 -> 작은 문제의 정답을 이용.

• 점화식의 정의

• D[N]=N을 1로 만드는 최소 연산 횟수.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

• N -> N/3 -> .... -> 1 => D[N]
• N/3 -> ... -> 1 => D[N/3]
• 1 + D[N/3]

2. X가 2로 나누어 떨어지면, 2로 나눈다.

• N -> N/2 -> .... -> 1 => D[N]
• N/2 -> ... -> 1 => D[N/2]
• 1 + D[N/2]

3. 1을 뺀다.

• N -> N-1 -> ... ->1
• 1 + D[N-1]

• D[N] = min(D[N/3]+1 , D[N/2]+1, D[N-1] + 1)

• N>=2만 사용 가능.

• 3으로 나누는 것, 2로 나누는 것, 1을 빼는 우선 순위로 N을 1로 만들어 본다.

• 이 방법으로는 정답을 구할 수 없다. (반례 10)

• 항상 최소를 구하는 방법인 다이나믹을 이용해서 풀면 된다.
  작게 만들 수 있는 모든 경우를 다 확인해보는 것이 중요!!

*top-down

• 재귀함수에서 조건중에 가장 중요한건, 가장 작은 크기의 문제를 처리해주는 조건문이 필요함.
• if(n==1) return 0;

• memoization

• if(d[n]>0) return d[n];

*bottom-up

• 가장 작은 크기인 0으로 초기화 후 점점 큰 문제로 계산을 해서 값을 찾아나간다.

보통 top-down은 재귀, bottom-up은 반복문으로 푼다.

먼저,bottom-up방법으로 풀어보았다.

import java.util.*;

public class Main {
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int d[] = new int[n+1];
		d[0]=1;
		d[0]=1;
		for(int i=2;i<=n;i++) {
			d[i]=d[i-1]+1;
			if(i % 2 ==0)
				d[i]=Math.min(d[i], d[i/2]+1);
			if(i % 3 ==0)
				d[i]=Math.min(d[i], d[i/3]+1);
		}
		System.out.println(d[n]);
	}
}

흠.. top-down 방법으로 풀었는데 시간초과가 나왔다.

import java.util.*;

public class Main {
	static int d[];
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		d = new int[n+1];
		System.out.println(cal(n));
	}
	
	public static int cal(int n) {
		if(n==1) 	return 0;
		if(d[n]>0)	return d[n];
		
		d[n]=cal(n-1) +1;
		
		if(n%3==0) {
			d[n]=Math.min(d[n], cal(n/3)+1);
		}
		if(n%2==0) {
			d[n]=Math.min(d[n], cal(n/2)+1);
		}
		return d[n];
		
	}
}

이유는,,, math.min함수 때문이였다;;ㅎㅎ

import java.util.*;

public class Main {
	public static int d[];
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		d = new int[n+1];
		System.out.println(cal(n));
	}
	
	public static int cal(int n) {
		if(n==1) 	return 0;
		if(d[n]>0)	return d[n];
		
		d[n]=cal(n-1) +1;
		
		if(n%3==0) {
			int tmp=cal(n/3)+1;
			if(d[n]>tmp) {
				d[n]=tmp;
			}
		}
		if(n%2==0) {
			int tmp=cal(n/2)+1;
			if(d[n]>tmp) {
				d[n]=tmp;
			}
		}
		return d[n];
	}
}

최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.