[백준 10430 파이썬] 나머지

[백준 10430 파이썬] 나머지

 

안녕하세요.

 

이번 문제는 계산식이 복잡하네요. 암산을 해보면... 딱, 잘 모르겠군요.

하지만 걱정할 필요는 없습니다. 계산 결과도 중요하지 않고 증명할 필요도 없으니까요!

백준 10430

 

문제 분석

'문제' 부분은 복잡하지만 그다지 중요하지 않고, A, B, C 세 값을 입력받아 4가지 연산 결과를 출력하면 간단히 해결될 것 같습니다.

 

답안

map 함수로 정수형 변수 A, B, C 입력을 넣고, 출력값은 손이 아플 것 같으니 문제에서 복붙하면,

출력 복붙 시 에러

에러가 나네요! 왜 그럴까요?

바로 곱셈 연산자를 x로 썼기 때문이죠. 컴퓨터 입장에선 변수도 문자열도 연산자도 아닌것이 혼란스럽나 봅니다.

(곱셈 연산자는 'AxB' 포스팅에서 복습해 볼 수 있어요.)

 

자, 다시 곱셈 연산자를 '*'로 수정하여 입력해 봅니다. (출력값 줄 나누기 (sep)는 '사칙연산' 포스팅에서 설명 드렸어요!)

곱셈 연산자 수정 출력

입력과 출력만 따라했을 뿐인데, 문제에 대한 답도 알아낼 수 있겠네요.

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

(A×B)%C는 ((A%C) × (B%C))%C 와 같을까? 같습니다!

하지만 수학적인 증명까지는 필요 없겠죠? (필요하면 맨 밑을 보세요.)

 

간단히 정답을 확인해 보도록 합니다.

제출 결과

 

이만 마치도록 하겠습니다.

읽어주셔서 감사합니다.

 

수학적 증명

그냥 재미삼아 생각해 보려고 합니다. 궁금한 사람만 보세요.

 

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

A, B 각각 C로 나누어 떨어지는 부분 (C*x)과 나머지 (소문자)로 분해해 봅시다.

 

A=C*n+a, B=C*m+b (a, b < C)

 

(A+B)%C = (C*(n+m)+a+b)%C 에서 C로 나누어 떨어지는 부분을 제외한다면 (a+b)%C 만 남겠죠?

만약, (a+b)>=C 라면 나머지는 a+b-C, (a+b)<C라면 나머지는 a+b 이겠네요.

 

((A%C) + (B%C))%C 에 적용해 봅시다.

((C*n+a)%C) + ((C*m+b)%C))%C = (a+b)%C

마찬가지로, (a+b)>=C 라면 나머지는 a+b-C, (a+b)<C라면 나머지는 a+b 겠죠!

 

이어서, 

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

이제 원리는 아실테니 같은 방법으로 식만 전개해 볼게요.

 

(A×B)%C = ((C*n+a)*(C*m+b))%C = (C^2*(n*m)+C*(m*a+n*b)+a*b)%C = (a*b)%C

((A%C) × (B%C))%C = ((C*n+a)%C) * ((C*m+b)%C))%C = (a*b)%C

두 식은 같군요.

 

여기까지 읽어주신 분들은 두배로 감사합니다.