[백준] 10430 번 : 나머지 - JAVA [자바]

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

10430번: 나머지

 

---

• 문제

 

 

 

 

 

매우 간단한 문제다!

 

 

※ 주의할점

1. 입력은 공백단위로 구분 된다.
2. 나머지를 구하는 문제라 변수를 정수형으로 계산한다.

 

 

---

 

• 풀이하기 전에 ...  모듈러 연산 ( Modular Arithmetic ) 과 증명

 

위 문제에서 그냥 출력만 하고 땡이지! 라고 하기에는 너무 아까운 문제다.

 

모듈러 연산이라고 들어보셨는지 모르겠다. ( 아마 대부분 배웠지 않았을까..? )

갑자기 모듈러 연산이라고? 라고 한다면 나머지와 관련된 연산식이 바로 모듈러 연산이다.

 

우리는 프로그래밍에서 대부분 나머지 연산 할 때 %로 표기하며 아래와 같이 표현한다.

17 % 3 = 2

이 것을 일반 표기법으로 바꾸면 다음과 같다.

17 mod 3 = 2

이제 표현 방법을 알았으니 왜 언급했는지 알려주겠다.

 

문제에서 총 4개의 케이스가 나왔다.

1. (A+B) %C 
2. (A%C + B%C)%C 
3. (A*B)%C 
4. (A%C * B%C)%C 

만약 이 문제를 풀어보신 분들을 알겠지만 컴파일 하여 자연수의 어떤 값이던 넣어보면 1번식과 2번식의 값이 같고, 3번식과 4번식의 값이 같다.

이는 모듈러 연산의 대표적 속성 두 가지를 보여주고 있다.

 

증명 방법을 보고 싶다면 아래 더 보기를 클릭하면 된다.

 

[증명 1] : (A+B) %C = (A%C + B%C)%C 

[증명]


증명 과정 자체는 매우 간단하다.

 

위 공식대로 풀면 되는데 하나하나 설명해보겠다.

먼저 a 와 b에 대해 c로 나눈 나머지 값을 mod 로 표현하여 정의한다. (이때 T 와 S 는 a 와 b 의 나머지다)

 

그럼 a와 b에 대하여 식을 변형 할 수 있는데 그게 바로 아래와 같은 것이다.

 

 

그럼 저 두 식을 갖고 우리가 증명하려는 식에 대입해보고 식을 정리해보자. 

 

 

 

위 식에서 느낌이 오는가?

c = 0 이 아닌 이상 ( i + j )*c 는 0 또는 3의 배수다.  

 

이 말은 i 와 j 의 값에 상관 없이 c의 배수이기 때문에 ( i + j )*c mod c = 0 이다.

즉 나머지 연산에서 ( T + S ) 의 나머지에 대하여 ( i + j )*c 는 위 식의 나머지 값에 대햐여 아무런 영향을 미치지 못한다.

 

그러므로 다음과 같이 쓸 수 있다.

 

 

그리고 T 와 S 는 처음 정의했듯이 각 각 a mod c 와 b mod c 이므로 이들로 교체해주면 우리가 증명하고자 한 공식이 완성된다.

 

 

증명 완료

 

[증명2] : (A*B)%C = (A%C * B%C)%C 

 

[증명2]

이 공식도 1번 증명 방법이랑 유사하다.

 

 

따로 하나하나 설명하지는 않겠다. ( 증명 1 을 이해한다면 이 것도 이해가 될 것이다. )

 

마찬가지로 곱셈을 풀어준 뒤 c 로 묶인 것들은 나머지 값에 영향을 미치지 못하므로 생략해주면 위 같이 공식이 성립함을 볼 수 있다.

 

 

 

 

 

 

---

• 2가지 입력방법을 이용하여 풀이한다.

 

 

Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다.

 

위 방법은 앞서 포스팅에서도 언급했으니 만약 쓰는 방법을 모른다면 아래 링크를 통해 읽어보는 것을 추천한다.

 

 

https://st-lab.tistory.com/12

[백준] 1000번 : A+B - JAVA [자바]

 

 

 

※Scanner 와 BufferedReader 의 입력방법에 대해 알아보고자 한다면 아래 링크의 포스팅을 보면 된다.

https://st-lab.tistory.com/41

JAVA [자바] - 입력 뜯어보기 [Scanner, InputStream, BufferedReader]

 

 

---

• 풀이

- 방법 1 

 

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int A = in.nextInt();
		int B = in.nextInt();
		int C = in.nextInt();

		in.close();

		System.out.println( (A+B)%C );
		System.out.println( (A%C + B%C)%C );
		System.out.println( (A*B)%C );
		System.out.println( (A%C * B%C)%C );
		
	}

}

 

가장 기본적인 방법이다. 하지만 Scanner 자체가 성능이 좋진 않으므로 필자는 다음과 같은 방법을 쓴다.

 

 

---

 

- 방법 2 

 

 

BufferedReader 을 쓰는 방식이다.

 

readLine() 을 통해 입력 받아 연산하는 방법 두 가지를 설명할 것이다.

앞서 말했듯이 readLine() 은 한 행을 전부 읽기 때문에 공백단위로 입력해 준 문자열을 공백단위로 분리해주어야 문제를 풀 수 있을 것이다.

 

문자열 분리 방법 두 가지로 풀어보자.

1. StringTokenizer 클래스를 이용하여 분리해주는 방법
2. split() 을 이용하는 방법

 

그리고 반드시 자료형 타입을 잘 보아야 한다.

st.nextToken() 은 문자열을 반환하니 Integer.parseInt()로 int 형으로 변환시켜준다.

(double 형으로 풀면 나머지가 정수로 나와도 소수점까지 같이 출력되어 오답으로 처리된다.)

 

// 방법 2-1

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

public class Main {

	public static void main(String[] args) throws IOException {
        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
 		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str," ");
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
        
		System.out.println( (A+B)%C );
		System.out.println( (A%C + B%C)%C );
		System.out.println( (A*B)%C );
		System.out.println( (A%C * B%C)%C );
	
/*    
굳이 String 변수 생성 안하고 입력과 동시에 구분자로 분리해줘도 된다.

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
        
		System.out.println( (A+B)%C );
		System.out.println( (A%C + B%C)%C );
		System.out.println( (A*B)%C );
		System.out.println( (A%C * B%C)%C );
*/
	}
}

 

 

 

 

두 번째 방법은 br.readLine() 을 통해 읽어온 것을 split(" ") 하여 공백 단위로 나눠준 뒤 String 배열에 각각 저장하는 방법이다.

 

 

// 방법 2-2

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

public class Main {

	public static void main(String[] args) throws IOException {
		     
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str = br.readLine().split(" ");
		int A = Integer.parseInt(str[0]);
		int B = Integer.parseInt(str[1]);
		int C = Integer.parseInt(str[2]);
        
		System.out.println( (A+B)%C );
		System.out.println( (A%C + B%C)%C );
		System.out.println( (A*B)%C );
		System.out.println( (A%C * B%C)%C );

	}

}

 

 

 

 

 

---

• 그 외 방법

 

필자는 시간 단축 (성능 개선)을 매우 좋아하는지라 필자가 사용한 방법이다.

 

 

BufferedReader + StringBuilder

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

		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);

	}
}

 

 

---

BufferedReader + BufferedWriter

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
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()," ");
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
        
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		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" );

		bw.flush();
		bw.close();

	}
}

 

 

 

---

• 성능 차이

 

위에서 부터 순서대로

 

채점 번호 : 17530320  -  BufferedReader + StringTokenizer +BufferedWriter 사용

채점 번호 : 17530311  -  BufferedReader + StringTokenizer + StringBuilder  사용

채점 번호 : 17530304  -  BufferedReader + String.split +  System.out.println() 사용

채점 번호 : 17530297  -  BufferedReader + StringTokenizer + System.out.println() 사용

채점 번호 : 17530285  -  Scanner + System.out.println() 사용

 

 

시간을 보면 BufferedReader 와 Scanner 의 성능차이가 확연하게 나는 것을 볼 수가 있다.

아직까진 출력이나 문자열 분리에서 성능차이가 눈에 보이지는 않는다.

 

아직까진 그냥 이런 방법들도 있구나~ 하면서 익혀두었으면 한다.

 

 

 

 

---

• 정리

 

문제는 간단했지만 모듈러 연산의 두가지 속성에 대해 알아두었으면 좋겠다 싶어 글이 길어졌다.

 

모듈러 연산은 암호시스템에서 사용 될 때가 있으므로 익혀둬서 나쁠 것은 없지 않은가.

모르는 부분이나 증명에서 궁금한 점 있으면 댓글 남겨주시면 감사하겠다.