[백준] 1463번 1로 만들기

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q1463.java

다음 3가지 연산을 이용해서 1로 만들 수 있는 최소의 연산 수를 구하여라.
1) 3으로 나눠 떨어진다면 3으로 나눈다.
2) 2로 나눠 떨어진다면 2로 나눈다.
3) 1을 뺀다.

처음 생각

생각나는건 2가지 방법이였다. BFS를 이용해서 3개의 연산을 차례로 진행해 나가면서 1로 만들어졌을 때 카운트 변수를 출력하는 방법과 다이나믹 프로그래밍을 이용해서 값을 찾는 방법이였다.

▶ 문제 분류가 DP로 되어있으므로 DP 식으로 풀어보았다.

다음 생각

생각을 단순히 하면서 접근을 해보자. 1로 만들수 있는 최소 연산 수를 구하는 법이다. Bottom Up 과 Top Down중 Bottom Up 방식을 사용하였다. 0~n의 index를 가지고있는 크기가 int[n+1]인 배열을 만들어 주었다.

▶ 1은 바로 1이므로 arr[1] = 0 이다.

▶ 최소값을 찾는 것이므로 모든 배열의 값은 큰 값으로 초기화를 시켜놓았다.

다다음 생각

index 1은 이미 0이므로 2부터 주어진 숫자 n까지 반복문을 통해 계산을 시작해주었다.

▶ i 번째 index인 arr[i]에 대해서 3가지 계산을 모두 해준다.

▶ i가 2로 나누어떨어진다면 arr[i]는 arr[i/2]+1 과 자기 자신인 arr[i] 중 작은 값을 취한다.

▶ i가 3으로 나누어떨어진다면 arr[i]는 arr[i/3]+1과 자기 자신인 arr[i] 중 작은 값을 취한다.

▶ arr[i]는 arr[i-1]+1과 자기 자신인 arr[i] 중 작은 값을 취한다.

▶ 연산 배열에 +1을 해주는 이유는 연산을 한 번 했기에 결과값을 +1 시켜준 것이다. 3개의 연산을 모두 진행하면서 i를 n까지 진행하면 arr[n] 즉 1부터 n을 만들 때 최소로 과정으로 n을 만들 수 있는 값이 저장된다.

방안

1) Java 풀이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

package baekjoon.q1000;   import java.io.IOException; import java.util.Arrays; import java.util.Scanner;   public class Q1463 {     public static void main(String args[]) throws IOException {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int[] arr = new int[n+1];         // 최소값을 찾는 것이므로 최대값으로 채워놓기.         Arrays.fill(arr,99999999);         // Bottom Up 방식으로 아래서 부터 올라가보자.         // 1로 만들기 이므로 자기자신은 0번 싸이클         arr[1] = 0;         for(int i=2;i<=n;i++){             // 2로 나눠질 경우             if(i%2==0) arr[i] = Math.min(arr[i],arr[i/2]+1);             // 3으로 나눠질 경우             if(i%3==0) arr[i] = Math.min(arr[i],arr[i/3]+1);             // -1 경우             arr[i] = Math.min(arr[i],arr[i-1]+1);             // 세가지 케이스중 가장 작은 값을 같도록 한다.         }         System.out.println(arr[n]);     } }