반응형
https://softeer.ai/practice/6284
💡 바이러스
- 단순한 수학문제였다.
- 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으로 선언해주었다.
반응형
'CO-TE > 소프티어' 카테고리의 다른 글
[구름 플랫폼] 2023 현대자동차 부트캠프 3기 코딩테스트 예제 풀이 (0) | 2023.11.18 |
---|---|
[소프티어] JAVA LV3 "슈퍼바이러스" 풀이법 / 분할과 정복 (0) | 2023.11.07 |
[소프티어] c++ LV2 "금고 털이" 풀이법 (0) | 2023.11.03 |
[소프티어] c++ LV3 "징검다리" 계수정렬 이용 풀이법 (0) | 2023.11.02 |
[소프티어] c++ LV3 "성적 평균" 풀이법 (제출 오류..?) (0) | 2023.11.01 |