백준 1463번 자바 ☆

문제

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

1463번: 1로 만들기

import java.util.Scanner;

public class Main1463_1 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] dp = new int[N + 1];

		for (int i = 1; i < N + 1; i++) {
			if (i==1) {
				dp[i] = 0;
				continue;
			}
			dp[i] = dp[i - 1] + 1;
			if (i % 3 == 0) {
				dp[i] = Math.min(dp[i / 3]+1, dp[i]);
			} 
			if (i % 2 == 0) {
				dp[i] = Math.min(dp[i / 2]+1, dp[i]);
			}
		}
		System.out.println(dp[N]);
	}
}

1. 바로 위 코드가 정답인 코드다. 아래 처음풀었던 코드가 계속틀리는데 반례를 찾지 못해 헤맸다.

 

2. 정답 코드와 내코드를 하나씩 비교하며 반례를 찾은 결과가 맨 밑에 마지막 코드이다. 

 

3. 내 코드에서 해결하지 못했던 부분은 -1을 해주는 부분에 있었다. 반례중 572를 보면 3으로는 나눠지지 않기에 

첫째, 2로 나눌때

둘째, -1했을 때 

두 가지의 경우로 나눠진다.

2로 나눴을때 arr[286], dp[286]의 값과 -1 했을 때 arr[571], dp[571]의 값은 같다.

 

하지만 정답코드의 경우, -1을 먼저하고 최소값을 비교한 반면

내 코드는 2또는 3으로 나눈후 -1한 값에 또 2또는 3으로 나누려 했다. 이 부분에서 arr[571]은 값의 비교대상에서 배제 됐기에 반례가 생긴것이다.

 

위 반례말고 처음 풀 때 2,3나누기 또는 -1 조건문을 if~else if문으로 표현했다. 3가지의 값을 비교해야 하는데 3가지중 하나만 선택돼서 로직이 진행되니 틀렸다. 

import java.util.Scanner;

public class Main1463_2 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] arr = new int[N+1];

		for (int i=1; i<=N; i++) {
			int div2Temp = Integer.MAX_VALUE;
			int div3Temp = Integer.MAX_VALUE;
			int minus1Temp = Integer.MAX_VALUE;
			
			if (i==1) {
				arr[i] =0;
				continue;
			}
			
			if (i%2==0) {
				if ((i-1)%3==0) {
					div2Temp = arr[(i-1)/3] + 2;
				}	
					div2Temp = Math.min(div2Temp, arr[i/2] + 1);
			} 
			
			if (i%3==0) {
				int temp = Integer.MAX_VALUE;
				if ((i-1)%2==0) {
					div3Temp = arr[(i-1)/2] +2;
				}
				if ((i-1)%3==0) {
					temp = arr[(i-1)/3] +2;
				}
					div3Temp = Math.min(temp, div3Temp);
					div3Temp = Math.min(div3Temp, arr[i/3] + 1);		
			} 
			
			if (i%2!=0 && i%3!=0) {
				minus1Temp = arr[i-1] + 1;
			}

			arr[i] = Math.min(div2Temp, div3Temp);
			arr[i] = Math.min(arr[i], minus1Temp);
		}
		
		System.out.println(arr[N]);
	}
}

import java.util.Scanner;

public class Main1463 {
	static int N;
	static int[] arr;
	static int[] dp;
	
	public static void a(int n) {
		
		for (int i=1; i<=N; i++) {
			int div2Temp = Integer.MAX_VALUE;
			int div3Temp = Integer.MAX_VALUE;
			int minus1Temp = Integer.MAX_VALUE;
			
			if (i==1) {
				arr[i] =0;
				continue;
			}
			
			if (i%2==0) {
				if ((i-1)%3==0) {
					div2Temp = arr[(i-1)/3] + 2;
				}	
					div2Temp = Math.min(div2Temp, arr[i/2] + 1);
			} 
			
			if (i%3==0) {
				if ((i-1)%2==0) {
					div3Temp = arr[(i-1)/2] +2;
				}
					div3Temp = Math.min(div3Temp, arr[i/3] + 1);		
			} 
			
			if (i%2!=0 && i%3!=0) {
				minus1Temp = arr[i-1] + 1;
			}

			arr[i] = Math.min(div2Temp, div3Temp);
			arr[i] = Math.min(arr[i], minus1Temp);
		}
	}

	public static void b(int N) {
		
		for (int i = 1; i < N + 1; i++) {
			if (i==1) {
				dp[i] = 0;
				continue;
			}
			dp[i] = dp[i - 1] + 1;
			if (i % 3 == 0) {
				dp[i] = Math.min(dp[i / 3]+1, dp[i]);
			} 
			if (i % 2 == 0) {
				dp[i] = Math.min(dp[i / 2]+1, dp[i]);
			}
		}

	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		arr = new int[N+1];
		dp = new int[N+1];
		
		a(N);
		b(N);

		for (int i=1; i<=N; i++) {
			if (arr[i] != dp[i]) {
				System.out.println("N값:"+i+" arr값:" +arr[i]+" dp값:" +dp[i]);
			}
		}
		
	}
}
// 입력 : 1000 
결과
N값:572 arr값:11 dp값:10
N값:734 arr값:10 dp값:9
N값:740 arr값:10 dp값:9
N값:842 arr값:12 dp값:11

4. 아래는 잘못됐던 내 코드를 다시 올바르게 고친 코드다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] arr = new int[N+1];

		for (int i=1; i<=N; i++) {
			int div2Temp = Integer.MAX_VALUE;
			int div3Temp = Integer.MAX_VALUE;
			int minus1Temp = Integer.MAX_VALUE;
			
			if (i==1) {
				arr[i] =0;
				continue;
			}
			
			if (i%2==0) {
				div2Temp = Math.min(arr[i-1]+1, arr[i/2] + 1);
			} 
			
			if (i%3==0) {
				div3Temp = Math.min(arr[i-1]+1, arr[i/3] + 1);		
			} 
			
			if (i%2!=0 && i%3!=0) {
				minus1Temp = arr[i-1] + 1;
			}

			arr[i] = Math.min(div2Temp, div3Temp);
			arr[i] = Math.min(arr[i], minus1Temp);
		}
		
		System.out.println(arr[N]);
	}
}

5. dp 자체 점화식을 세우는 일도 쉽지 않지만 반례를 찾는 일 또한 쉽지 않다. 지금이야 바로바로 비교 가능하니 풀었는데 만약 코딩 테스트중인 상황이면 짜여진 코드만으로 쉽게 반례를 찾지 못할 듯 하다. 항상 반례를 찾기위해 머리를 비우고 새로 시작한다는 생각으로 코드를 바라보는 습관을 길들여야한다.