이것이 취업을 위한 코딩 테스트다. 그리디 [1이 될 때까지]

이것이 취업을 위한 코딩 테스트다. with 파이썬 - 나동빈

나의 풀이

public class UntilItBecomeOne {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String[] split = str.split(" ");
        int count = 0;

        int N = Integer.parseInt(split[0]);
        int K = Integer.parseInt(split[1]);

        while(N != 1) {
            if(N % K == 0) {
                N = N / K;
                count++;
            } else {
                N--;
                count++;
            }
        }

        System.out.println(count);
    }
}

• 숫자 N과 K 값을 입력받는다.
• N이 1이 될 때까지
  • N 이 K 의 배수이면 나눠주고 아니면 -1 을 한다.

문제 해설 & 느낀점

문제에서는 N의 범위가 10만 이하이므로, 1씩 빼도 문제를 해결할 수 있다. 하지만 100억 이상의 큰 수가 되는 경우라면 효율적으로 1씩이 아닌, 한 번에 빼는 방식으로 작성해야 한다.

while (true) {
// N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
int target = (n / k) * k;
result += (n - target);
n = target;
// N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
if (n < k) break;
// K로 나누기
result += 1;
n /= k;
}

// 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1);
System.out.println(result);

• 처음에는 (n / k) k 가 이해가 되지 않았다. (17 / 4) 4 = 17 이라 생각했기 때문이다.
• 하지만 17 / 4 는 int 로 반환되기 때문에 뒤에 소수점은 다 없어지고 몫인 4만 나온다. 그렇기 때문에 4 * 4 = 16 즉 17 에서 1을 뺀 것과 같은 효과가 난다.