10430 번 : 나머지

• 🤜🏻 주의할 점

  • 입력은 공백단위로 구분된다.

  • 나머지를 구하는 문제라 변수를 정수형으로 계산한다.

• 🤜🏻 풀이 전 모듈러 연산(Modular Arithmetic) 과 증명

  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) 식의 값이 같다.

  Set.

  a mod c = T

  b mod c = S

  a = T + ic(i는 임의의 정수)

  b = S + jc(j는 임의의 정수)

  (a + b) mod c = ((T+ic)+(S+jc)) mod c

  = ((T+S) + (i+j)c) mod c

  = (T+S) mod c

  = ((a mod c) + (b mod c)) mod c

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

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

  Set.

  a mod c = T

  b mod c = S

  a = T + ic (i는 임의의 정수)

  b = S + jc (j는 임의의 정수)

  이 두 식을 갖고 증명하려는 식에 대입해보면

  (a+b) mod c = ((T+ic) + (S + jc)) mod c

  = ((T+S) + (i+j)c) mod c

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

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

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

  (a+b) mod c = ((T+ic) + (S + jc)) mod c

  = ((T+S) + (i+j)c) mod c

  = (T+S) mod c

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

  (a + b) mod c = ((T+ic) + (S+jc)) mod c

  = ((T+S) + (i+j)c) mod c

  = (T+S) mod c

  = ((a mod c) + (b mod c)) mod c

  Set.

  a mod c = T

  b mod c = S

  a = T + ic (i는 임의의 정수)

  b = S + jc (j는 임의의 정수)

  (a * b) mod c = ((T+ic) * (S+jc)) mod c

  = ((TS) + Tjc + Sic + (ij)c^2) mod c

  = ((TS) + (Tj + Si)c + (ij)c^2) mod c

  = (TS) mod c

  = ((a mod c) * b mod c)) mod c

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

• 🤜🏻풀이방법(2가지)

  1) Scanner로 입력받아 연산

  2) BufferedReader로 입력받아 연산

• 🤜🏻방법1 - Scanner

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

• 🤜🏻방법2 - BufferedReader

  BufferedReader 를 사용

  readLine() 을 통해 입력 받아 연산하는 방법 두가지로 나뉨

  readLine은 한 행을 전부 읽기 때문에 공백 단위로 입력해 준 문자열을 공백 단위로 분리해주어야 함.

  • 1) StringTokenizer 클래스 사용

    st.nextToken()은 문자열을 반환하니 Integer.parseInt()로 int 형변환 시켜주어야 함.

    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));
    		
    		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);
    		*/
    	}
    }

  • 2) split() 사용

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    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);
    	}
    }

• 🤜🏻그 외 방법3(2가지 - 성능개선)

  • 1) BufferedReader + StringBuilder

    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(), " ");
    		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);
    	}
    }

  • 2) BufferedReader + BufferedWriter

    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.OutputStreamWriter;
    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();
    	}
    }

Uploaded by Notion2Tistory v1.1.0