그리디 공부하기(동빈나)

https://www.youtube.com/watch?v=2zjoKjt97vQ&t=20s 

문제 1

 

import java.util.Scanner;
public class Main
{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        
        //내가 한 방법..
        int result = 0;
        while(N>1){
            if(N%K>0){
                N--;
                result++;
            }else{
                N=N/K;
                result++;
            }
        }

        System.out.println(result);
        
        //알고리즘
        while(true){
            int target = (N/K) * K; // N이 K로 나누어 떨어지는 가장 가까운 수 구하기.
            result += (N-target); //가장 가까운 수 될때까지 1씩 뺀 횟수
            N=target;// 앞으로 1로 만들어야할 남은 수
            
            if(N < K) break;
            
            N /= K; //K로 나눔(위에서 나누어지는 수로 바꿈)
            result += 1;//한번 연산했으니 +1 해줌
        }
        
        result += (N-1); // N이 1보다 클때 남은수에서 1이 될때까지 빼야하는 횟수 더하기
        System.out.println(result);
        
    }
}

 

 

 

0731  복습

import java.util.Scanner;
public class Main
{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        
        int result = 0;
        while(N >= K){
            int target = (N/K) * K;
            result += (N - target);
            N=target;

            N /= K;
            result+=1;
        }
        
        result += (N-1);
        System.out.println(result);
        
    }
}

왜 break로 while문을 빠져나올때 저 저 중간에서 빠져나오는지 모르겠다. 

애초에 밑에단계에서 N이 K보다 작아졌을때 빠져나오면 될 거 같은데..

위쪽에서 계산했을때 N이 K보다 큰 상황이지만 계산후 N이 K보다 작아지는경우가 있어서 그러는걸까.?(그럴수가 있나..?)

모르것다 ..

아부지 정답을알려줘