백준 #10430: 나머지 (JAVA/Java)

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

10430:나머지

첫 번째 줄에는 A, B, C가 순서대로 표시됩니다. (2≤A,B,C≤10000)

'추천 관련글,

www.acmicpc.net

쉬운 목차

ㆍ 솔루션

문제는 세 개의 숫자 A, B, C가 주어졌을 때 위의 네 가지 값을 계산하는 프로그램을 작성하는 것입니다.
간단한 출력 문제이므로 위 식을 그대로 인용하여 출력하면 됩니다.
3개의 정수는 BufferedReader 클래스를 통해 문자열로 입력되며 입력 값은 StringTokenizer를 사용하여 공백을 기준으로 분할됩니다.
문자열은 정수 유형이 아니므로 유형 변환을 거쳐 BufferedWriter 클래스를 사용하여 네 가지 값에 대한 작업을 내보냅니다.

단순한 출력 문제이지만 이 문제는 나머지 연산의 특징을 담고 있다.
우리가 확인하고자 하는 나머지 연산의 분배법칙의 성질이 있다.

(A+B) % c = ((A%C) + (B%C)) %C

위 알고리즘 문제의 샘플 입력값인 5, 8, 4를 대입하여 증명하시오.
A의 몫과 나머지를 x1 / y1이라고 가정하면 A = x1 XC + y1로 표현할 수 있습니다.

A = x1 X C + y1

= A의 몫 X C + A의 나머지
= 1 X 4 + 1 = 5

A = 5

B의 몫과 나머지를 x2 / y2라고 가정하면 B = x2 XC + y2로 표현할 수 있습니다.

B = x2 X C + y2

= B의 몫 X C + B의 나머지
= 2 X 4 + 0 = 8

B = 8

위의 A와 B는 이렇게 교체할 수 있습니다.

(A+B) % C = (x1 X C + y1 + x2 X C + y2) % C

= ((x1 + x2) X C + y1 + y2) % C

위 식(x1 + x2)에서 XC에서 %C 연산을 하면 나머지는 0이 된다.

((x1 + x2) X C) % C
= (1 + 2) X 4 = 12
= 12 % 4 -> 0
= 나머지 0

나머지 식은 (y1 + y2) % C입니다.
y1은 A에서 C의 모듈러스 연산 값(나머지)이고 y2는 B에서 C의 모듈러스 연산 값이므로 다음과 같이 나타낼 수 있습니다.

y1 = A % C
y2 = B % C

따라서 위의 표현이 성립합니다.

(A+B) % c = (y1 + y2) % C
-> 남은 식

(A+B) % c = ((A%C) + (B%C)) %C

ㆍ 소스코드

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    public static void main(String() args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        bw.write(((A+B)%C) + "\n");
        bw.write((((A%C) + (B%C))%C) + "\n");
        bw.write(((A*B)%C) + "\n");
        bw.write((((A%C) * (B%C))%C) + "\n");


        br.close();
        bw.flush();
        bw.close();
    }
}