[코드트리/NL] 나눗셈의 나머지

✏️ 문제 설명

두 정수 a, b가 주어지면, a를 b로 나눈 몫을 a에 계속해서 저장하는 것을 반복하려고 합니다.

a가 1이하가 되기 전 까지 나눗셈을 반복한다고 할 때, 각 나눗셈 연산마다 나온 나머지들이 등장한 횟수를 제곱하여 그 합을 출력하는 프로그램을 작성해보세요.

예를 들어, a = 1000, b = 4인 경우 나눗셈은 다음과 같이 진행됩니다.

• 1000÷4=250 ... 0
• 250÷4=62 ... 2
• 62÷4=15 ... 2
• 15÷4=3 ... 3
• 3÷4=0 ... 3

5번의 나눗셈 동안 나머지는 0이 1번, 2가 2번, 3이 2번 등장했으므로, 각 나머지가 나온 횟수의 제곱의 합은 12+22+22=9 입니다.

---

✏️ code

📌 고민했던 부분

• arr[a%b]++의 순서
  • 현재 코드에서는 나머지 계산이 먼저 이루어지고, 그 후에 a/b를 나누는 순서로 되어 있습니다.
  • 이렇게 해야 각 나누기 전에 나온 나머지를 정확히 기록할 수 있기 때문입니다.
  • 만약 순서를 바꾸어, 나누기 후에 나머지를 계산하고 증가 시킨다면 잘못된 나머지가 기록될 수 있습니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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().trim());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int arr[] = new int[10];
        int sum = 0;

        while (a > 1) {
            arr[a%b]++;
            a /= b;
        }

        for (int i = 0; i < 10; i++) {
            sum += arr[i]*arr[i];
        }

        System.out.print(sum);

        br.close();
    }
}

 

---

https://www.codetree.ai/missions/4/problems/remainder-of-division/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석