[JAVA] 25418번 - 정수 a를 k로 만들기

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

세 가지 방법으로 풀었다.

1) greedy로 풀기

2) DP로 풀기

3) BFS로 풀기

 

1) greedy로 풀기

반대로 생각하면 K를 A로 만들어야한다.

그러면 2로 나누거나 or 1을빼면 된다

a. 숫자가 짝수면 2로 나눈다 (나누는게 더 이득이라 최소 횟수가 되니까) 

b. 숫자가 홀수면 1을 빼면 된다

여기에 중요한게 있다. 

8은 2로 나누면 4가 되는데 그럼 7이 되지 못한다. 조건 하나를 더 추가한다

+ 2로나눈수가 a보다 클때만 2로 나눈다

 

 

2) DP로 풀기

이 문제를 처음 봤을때 가장 먼저 떠올린 풀이는 DP이다.

왜 DP로 풀 수 있느냐!! 큰 문제를 작은 문제로 쪼갤 수 있고, 재활용 할 수 있기 때문이다

다시 말해, 7->8->9->18->19->38->76->77인데

8의 경우 8->9->18->19->38->76->77

9의 경우 9->18->19->38->76->77 이다

즉 8의 경우를 구할때 9의 결과를 이용한다

그럼 8의 경우는 9를구하는 최소연산 + 1 이다.그렇기에 dp로 풀 수 있다.

예전에 1로 만들기랑 비슷하게 접근하면 될 것같아서 고론식으로 풀어보았따!!

 

18을 예시로 들어보면!

18은 17에서 18이 될 수 있고, 9에서 18이 될 수 있다. 즉

17로 만드는 최소 연산 횟수에서 +1

9로 만드는 최소 연산 횟수에서 + 1 이다

여기서 각 +1은 각 연산의 횟수이다 9에서 2를 곱하거나 17에서 1을 더하거나이다.

일반화하자면

dp[n-1] + 1
dp[n/2] + 1

 

이 둘중에 최소값을 구하면된다 최소연산횟수를 구해야하기 때문이다!!

2로 나누는건 짝수이고 n/2>=a보다 클때만 가능하니까 이 조건만 추가하면 된다

일반화조건을 이해하는데 1로 만들기를 푼 덕분에 풀 수 있었다

 

 

3)  BFS로 풀기

이 문제를 BFS로 풀 수 있는건 전혀 상상도 못했다

A에서 K가 되는 최단 경로를 찾는다고 접근할 수 있어서 BFS로 풀 수 있다.

한 번 연산할때 도달할 수 있는 모든 숫자들을 탐색하니까, 최소 경로를 보장가능

 

1. 숫자 A를 큐에 넣고 꺼낸다 연산 횟수는 0

2. 방문할 수 있는 모든 구역탐색= A+1 연산과 A*2연산을 큐에 넣는다 

3. 이때 새로 생성된 숫자가 K보다 크면 종료, K에 도달할 때까지 연산 횟수 출력 

 

 

 

 

 

 

 

시간복잡도

1) greedy로 풀기

짝수일때는 2로 나누니까 log(k)이다.

홀수일때는 1을 빼니까 선형시간복잡도다

O(log(k-a))이다 k와 a는 각각 최대 1,000,000이니까 O(6)으로 아주 넉넉하다

 

2) DP로 풀기

A+1부터 K까지 확인하면 된다 

O(K-A)이다. 최악의 경우 A가 0이고 K가 1,000,000인 경우니까 O(1,000,000)이다

 

3) BFS로 풀기

큐에 들어가는 숫자는 최대 1,000,000이다 O(K)이다 O(1,000,000)

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1) greedy로 풀

-> 간단한 조건문으로 해결할 수 있다.

 while(tmp!=a) {
        	if(tmp%2==0 && (tmp/2)>=a) { 
        		tmp=tmp/2;
        	}
        	else {
        		tmp--;
        	}
        	cnt++;
        }

 

 

2) DP로 풀기

반복문을 돌때 시작부분을 A+1에서 시작해야한다. A보다 작은수는 모두 0이기 때문

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

1) greedy로 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int tmp =k;
        int cnt = 0;
        while(tmp!=a) {
        	if(tmp%2==0 && (tmp/2)>=a) { 
        		tmp=tmp/2;
        	}
        	else {
        		tmp--;
        	}
        	cnt++;
        }
        System.out.println(cnt);
        
        
        
    }
  
}

 

 

2) DP로 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int dp[] = new int[k+1];
        
        //a미만은 전부 0이기 때문에 a+1부터 시작 
        for(int i= a+1; i<=k; i++) {
        	dp[i] = dp[i-1] + 1;
        	if(i%2==0 && i/2>=a) {
        		dp[i] = Math.min(dp[i], dp[i/2]+1);
        	}
        }
        System.out.println(dp[k]);
        
        
    }
  
}

 

 

3) BFS로 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        bfs(a,k);
        
        
    }
private static void bfs(int a, int k) {
	 Queue<int[]> q = new LinkedList<>();
     boolean[] visited = new boolean[k+1];
     q.add(new int[] {a,0});
     while(!q.isEmpty()) {
    	 int p = q.peek()[0];
    	 int cnt = q.peek()[1];
    	 q.remove();
    	 
    	 if(p==k) {
    		 System.out.println(cnt);
    	 }
    	 if(p+1 < visited.length && !visited[p+1]) {
    		 q.add(new int[] {p+1, cnt+1});
    		 visited[p+1] = true;
    	 }
    	 if(p*2 < visited.length && !visited[p*2]){
             q.add(new int[]{p*2, cnt+1});
             visited[p*2] = true;
         }
    	 
    }
     

}
  
}