[백준] 1463번 1로 만들기 JAVA (자바) 풀이

문제 1463번 

 :  정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지

1. X가 3으로 나누어 떨어지면, ÷ 3
2. X가 2로 나누어 떨어지면, ÷ 2
3. - 1

    위와 같은 연산 세 개를 사용해서 N = 1을 만들려고 할 때 연산의 최소 횟수를 출력

 

[입력]

 :  첫 줄에 N (1 ≤ N ≤ 106)

 

 

[출력]

 :  첫째 줄에 연산을 하는 횟수의 최솟값을 출력

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

1) Top-down(하향식)

     하위 문제를 재귀적으로 호출하여 해결함으로서 상위 문제를 해결하는 방식
     이 때 해결해놓은 하위 문제를 저장해 놓기 위해 Memoization사용

 

public class Topdown {
	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		System.out.println(fibo(n));
		
	}
	
    // Top-down
	static int fibo(int x) {
		if( x ==1 || x==2) return 1;
		if(dp[x] != 0) return dp[x];
		dp[x] = fibo(x-1) + fibo(x-2);
		return dp[x];
	}
}

 

2) Bottom-up(상향식)

 

    하위에서부터 문제를 먼저 해결하고 얻어진 값들을 이용해서 상위 문제를 해결해나가는 방식

    반복문을 사용해서 구현하고 문제의 결과 값을 저장하는 리스트는 DP 테이블이라 부른다

    

public class Bottomup {

	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		
		System.out.println(fibo(n));
	}
	
    // Bottom-up
	static int fibo(int x) {
		dp[1] =1;
		dp[2] =1;
		for(int i=3; i<x+1; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[x];
	}

 

 

[문제 설명]

• 2와 3은 직관적으로 판단 가능하다
  둘 다 연산 횟수는 1이다
• 여러 연산이 가능하지만 편의상 하나씩만 썼다
  ( 예를 들면 <4> 연산방법으로 ÷ 2 - 1 해도 된다 )
  
  
• 연산 규칙은 무조건 세 가지 해보고 제일 작은거 고르면 된다
  세가지: ÷ 3해보고 ÷ 2해보고 - 1해보고 나온 index값의 연산횟수에서 +1 만 해준다
  
  
• 참고영상
  
  

  

  
  [예시1]
  index <6> 라면
  
  1. ÷ 3해서 나온 index값 + 1
  ÷ 3해서 나온 index는 <2>이다
  우리는 위에서 index <2>의 연산 횟수를 미리
  구해놓았다 ( <2> 연산 횟수 = 1 )
  여기서 + 1 해주면 되는데, 왜 +1을 해주냐면
  우리가 ÷ 3 해서 나온 값이기 때문에 그연산까지
  합쳐서 횟수로 포함하므로 + 1 
  즉 <6>의 연산 횟수는 2이다
  
  2. ÷ 2해서 나온 index값 + 1
  ÷ 2해서 나온 index는 <3>이다
  <3>의 연산횟수는 1이고 + 1을 더해주면
  <6>의 연산 횟수는 2이다
  
  3. -1해서 나온 index값 + 1
  -1해서 나온 index는 <5>이다
  <5>의 연산횟수는 3이고 + 1을 더해주면
  <6>의 연산횟수는 4이다
  
  1,2,3번 중 가장 최소값은 2이다

 

[탑다운 코드]

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[1000001];  //DP 배열 초기화
        dp[2] = 1;
        dp[3] = 1;
        for (int i = 4; i <= n; i++) {
            if (i % 6 == 0) {
                dp[i] = Math.min(dp[i/3], Math.min(dp[i/2], dp[i-1])) + 1;
            } else if (i % 3 == 0) {
                dp[i] = Math.min(dp[i/3], dp[i-1])+1;
            } else if (i % 2 == 0) {
                dp[i] = Math.min(dp[i/2], dp[i-1]) + 1;
            } else {
                dp[i] = dp[i-1] + 1;
            }
        }
        System.out.print(dp[n]);
    }
}

 

 [해설]     

 :  int n = Integer.parseInt(br.readLine());  첫째줄 입력받기
       

 :  int[] dp = new int[1000001];  DP 배열 초기화
       
 :  dp[2] = 1;  2는 쉽게 파악 가능해서 초기화
    dp[3] = 1;  3도 쉽게 파악 가능해서 초기화

 :  for (int i = 4; i <= n; i++) {  3까지 초기값 설정했으니 4부터 판단 시작
           if (i % 6 == 0) {  3과 2 둘 다 나누어 떨어질 때 
                dp[i] = Math.min(dp[i/3], Math.min(dp[i/2], dp[i-1])) + 1;  가장 최소값에서 + 1 
           }
           else if (i % 3 == 0) {  3으로만 나누어 떨어질 때
                dp[i] = Math.min(dp[i/3], dp[i-1])+1;  가장 최소값에서 +1
           }
           else if (i % 2 == 0) { 2로만 나누어 떨어질 때
                dp[i] = Math.min(dp[i/2], dp[i-1]) + 1;  가장 최소값에서 +1
           }
           else {  3과 2 둘다 나누어 떨어지지 않을 때
                dp[i] = dp[i-1] + 1;  -1 연산 밖에 없음 그 값에서 + 1 
           }
   }
 

 :  System.out.print(dp[n]);  해당 dp 값 출력

  

 

 [보텀업 코드]

import java.util.Scanner;
import java.lang.Math;

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

        int[] dp = new int[N+1];

        dp[1] = 0;

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

        System.out.print(dp[N]);
    }
}

 

 [해설]     

 

 :  int N = sc.nextInt();  첫째줄 입력

 :  int[] dp = new int[N+1];  dp 생성
    dp[1] = 0;  dp[1] 값 초기화

 :  for(int i=2; i<= N; i++) {  2부터 시작
          dp[i] = dp[i-1] + 1;  바로 전의 index 값을 확인하기 위해 -1 연산부터 시작
           if(i % 2 == 0){  만약 2로 나눠 떨어지면
                 dp[i] = Math.min(dp[i], dp[i/2] + 1);  -1이나 ÷2 중에 더 작은 값 구하기
            }
            if(i % 3 == 0) {  만약 3으로 나눠 떨어지면
                dp[i] = Math.min(dp[i], dp[i/3] + 1);  -1이나 ÷3 중에 더 작은 값 구하기
            }
   }

 :  System.out.print(dp[N]);  출력

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

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

1463번: 1로 만들기

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *