| 문제
| 해결
이 문제는 사실 출력만 하는거라 어렵지 않았다. 출력방법은 Scanner, BufferedReader 둘 중 하나를 사용하여 해주면 될것 같다.
*주의할 점
1. 한 줄에 한 개의 결과값을 출력해야 한다.
2. 나머지를 구해야하므로 변수를 int로 계산해야 한다.
먼저, 코드를 적기전에 왜 각각 두개의 식들이 같은지 증명을 하고 이해하면 좋을것 같아서 정리해보게 되었다.
위와같이 나머지와 연관된 식들을 모듈로 연산이라고 한다.
| 모듈로 연산(Modulo Operation)
- 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다.
- A mod B 와 같은 형태로 표현한다. ( A % B = A mod B)
문제에서는 총 4개의 케이스가 나왔다.
- (A+B) %C
- (A%C + B%C)%C
- (A*B)%C
- (A%C * B%C)%C
1과 2의 케이스의 결과값이 같으며 3과 4의 결과값이 같다. 이것은 모듈로 사칙 연산의 대표적인 속성을 보여준다.
이제부터 이 두가지를 증명해보겠다.
| (A+B) %C = (A%C + B%C)%C
A mod C = T
B mod C = F
A = T + iC (i는 임의의 정수)
B = F + jC (j는 임의의 정수)
(A+B) mod C = ( (T+iC) + (F+jC) ) mod C
= ( (T+F) + ( i+j )C ) mod C
= ( T+F ) mod C
= ( (A mod C) + (B mod C) ) mod C
위의 식으로 증명할 수 있는데 하나 하나 예를 들어 설명해보겠다. 아래와 같이 두개의 식이 있다고 해보자.
1) 10/3= 3..1 ( 10 mod 3 = 1)
2) 8/3= 2..2 ( 8 mod 3 = 2)
두개의 식은 결국 아래의 두개의 식과 동일하다.
1)10= 1 + 3*3
2) 8= 2 + 3*2
(10+8) mod 3 = ( (1+3*3) + (2+3*2) ) mod 3
= ( (1+2) + ( 3+2 )3 ) mod 3
= ( 1+2 ) mod C
= ( (1 mod 3) + (8 mod 3) ) mod 3
여기서 (3+2)3 은 3의 배수이므로 mod 3 식을 만나면 무조건 나머지가 0 이 된다. 이 말은 즉 나머지를 구하는데 있어 (3+2)3 은 어떠한 영향력도 끼치지 않는다는 것이다. 그러므로 (1+2) 로 식을 줄일 수 있다. 결국 1 과 2 는 (1 mod 3) + (8 mod 3) 이므로 (A+B) %C = (A%C + B%C)%C 의 식을 증명한다는 것을 보여준다.
| (A*B) %C = (A%C * B%C)%C
A mod C = T
B mod C = F
A = T + iC (i는 임의의 정수)
B = F + jC (j는 임의의 정수)
(A*B) mod C = ( (T+iC) * (F+jC) ) mod C
= ( TF + TjC + iCF + iCjC² ) mod C
= ( TF + C(Tj + Fi) + iCjC² ) mod C
= ( TF ) mod C
= ( (A mod C) * (B mod C) ) mod C
앞서 말한것처럼 Tj와 Fi 값에 상관없이 C의 배수인것들은 영향을 끼치지 못하므로 제외한다고 생각하면 된다.
다른것들은 위와 동일하다.
출처:https://st-lab.tistory.com/19
| 풀이
풀이는 정말 간단하게 출력만 하는것이라 어렵지 않게 풀었다.
이번에는 scanner를 사용하여 풀었다.
'알고리즘 & 자료구조 > 수학1' 카테고리의 다른 글
| [백준]6588번 - 골드바흐의 추측(JAVA) (0) | 2022.05.01 |
|---|