[백준 BOJ 10430번] 나머지

출처 : https://www.acmicpc.net/problem/10430

10430번: 나머지

 

1. 문제

(A+B)%C는 ((A%C) + (B%C))%C 와 같을까?

(A×B)%C는 ((A%C) × (B%C))%C 와 같을까?

세 수 A, B, C가 주어졌을 때, 위의 네 가지 값을 구하는 프로그램을 작성하시오.

---

2. 입력

첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)

5 8 4

---

3. 출력

첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다.

1
1
0
0

---

4. 풀이

일단 이 문제는 <모듈러 연산>이라는 중요한 개념이 있다. 풀이하는 데에 있어서는 최대값이 10000*10000(1억<약21억(int))이므로 딱히 자료형에 제한을 받지 않으니 안심해도 된다.

먼저 모듈러 연산을 살펴보자.

 

참고: https://xerathcoder.tistory.com/70

모듈러 연산(Modular Arithmetic)

 

이를 통해 나머지 연산을 좀 더 쉽게 할 수 있다. 이 연산은 후에 여러 제한을 받거나 시간적 문제 해결이 요하는 문제에서 큰 역할을 한다.

문제 풀이는 단순히 식을 StringBuilder에 넣어서 출력들을 해주었다.

---

5. 소스코드

import java.io.BufferedReader;
import java.io.IOException;
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()," ");
        StringBuilder sb = new StringBuilder();
        
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        sb.append((A+B)%C);
        sb.append('\n');
        sb.append(((A%C)+(B%C))%C);
        sb.append('\n');
        sb.append((A*B)%C);
        sb.append('\n');
        sb.append(((A%C)*(B%C))%C);     
        System.out.println(sb);
    }
}

---

6. 배운 것

모듈러 연산을 잘 알아두자. 그 성질을 아는 것도 중요하지만 어떤 식으로 그 성질을 이용해서 시간을 단축하거나 계산을 작은 자료형 내에서 할 수 있는지를 알아두어야 한다.