[소프티어] JAVA LV2 "바이러스" 풀이법

https://softeer.ai/practice/6284

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

💡 바이러스

• 단순한 수학문제였다.
• K에 P를 N번 곱한 후 그값을 1000000007로 나눈 값을 출력하는 문제인데, 그냥 곱할 경우에는 int나 long에 완전히 담을 수 없을 정도로 숫자가 커지기 때문에, 일정한 값으로 나누어 져야 한다.
• K에 P를 곱한 후 1000000007로 나눈 나머지를 K에 다시 저장한 후, 그 나머지에 P를 곱하고 또 1000000007로 나눈 나머지를 K에 저장하는 식으로 해결할 수 있다. 이를 N번 반복한다.
• 어떻게 그게 가능할까?
• 만약 K=3, P=5, N=3,D(나누는 값)=13이라고 해보자.
  1R : 3*5=15, 15%13=2
  2R : 2*5=10, 10%13=10
  3R : 10*5=50, 50%13=11
  답:11
  한번에 했을 때 : 3*5*5*5%13 = 375%13=11
  답 11
  
  결과는 동일하다.
  
  15*5%13==(13*5%13)+(2*5%13)
  위와 같이 15 는 13,2로 분배될 수 있기 때문이다. 어차피 13만큼의 몇배던 13의 배수이므로 그 나머지는 0이되기때문에, 2만큼에 몇 배수를 한 것의 13으로 나눈 나머지만 구하면 된다.
• 전체 코드는 아래와 같다.
  

  import java.io.*;
  import java.util.*;
  
  public class Main {
  
      public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long K = scanner.nextInt();
        int P = scanner.nextInt();
        int N = scanner.nextInt();
        int d = 1000000007;
  
        for(int i=0; i<N; i++){
          K=(K*P)%d;
        }
        
        System.out.println(K);
        
      }
  }​

• 참고로 입력 값인 K와 P를 곱했을 때의 최대값의 범위가 10^18~10^19까지 나올 수 있기 때문에 계속해서 갱신되어야 할 K는 long으로 선언해주었다.