반응형
https://softeer.ai/practice/6292
💡 슈퍼바이러스
- lv1의 "바이러스" 업그레이드 버전
- 입력받는 크기가 더 커지기 때문에, 단순히 for문으로 해결하려고 하면, 시간초과가 발생한다.
- 따라서 분할과 정복을 통해 해결해야 한다.
- 즉 입력받은 n을 절반씩 쪼개가면서 분할 하고, 다시 합해가면서 전체 문제를 해결하는 방식이다.
- 이를 위해 solve라는 함수를 생성할 것이고, solve안에서는 solve함수를 재귀적으로 호출하면서 절반씩 나누어 해결한다.
- 코드를 통해 살펴보자.
public static long solve(long P, long N){
if(N==1) return P;
long res = solve(P, N/2);
if(N%2==0){
return (res*res)%D;
}
else{
res*=res;
res%=D;
return (res*P)%D;
}
}
- solve함수는 배수인 P와 거듭 수인 N을 입력으로 받는다.
- N이 1이면 P를 반환한다
- 그렇지 않다면, res를 선언하여 N의 절반만큼 P를 거듭 제곱한 값을 solve를 통해 구하고 저장한다.
- 만약 N이 짝수였다면, res를 두번 곱한 것에 1000000007을 나눈 나머지 값을 반환하면 된다.
- 만약 N이 홀수라면, res를 두번 곱한 것에 1000000007을 나눈 나머지에 P를 한번더 곱해주고 또 1000000007을 나눈 나머지를 반환하면 된다. 왜냐하면 홀수의 경우 나누었을 때 나머지 1이 있기 때문에, P를 한번더 곱해주어야 한다는 의미이다.
- 위의 solve함수를 통해 P의 n거듭제곱 하여 1000000007로 나눈 나머지를 구할 수 있으며, 최종적으로는 k에 곱했어야 했기 때문에, K에 곱한 값에 다시한번 1000000007로 나눈 나머지를 구하면, 답이 된다.
- 전체 코드는 아래와 같다.
import java.io.*;
import java.util.*;
public class Main {
static long D = 1000000007;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long K = scanner.nextLong();
long P = scanner.nextLong();
long N = scanner.nextLong();
N*=10;
long res = solve(P,N)*K;
res%=D;
System.out.println(res);
}
public static long solve(long P, long N){
if(N==1) return P;
long res = solve(P, N/2);
if(N%2==0){
return (res*res)%D;
}
else{
res*=res;
res%=D;
return (res*P)%D;
}
}
}
이 문제를 풀면서 한가지 알게 된 사실은, long 타입을 입력받을 땐 nextLong으로 받아야 한다는 점이다.
주 언어였던 c++에서 코테를 위한 java를 병행하여 배우면서 입력을 사용한지 얼마 안되었는데, next~가 세부적으로 존재한다는 것을 알게되었다. nextInt로 받으니 long으로의 변환에서 데이터 손실이 있어 결과가 잘 나오지 않았었다.
반응형
'CO-TE > 소프티어' 카테고리의 다른 글
[소프티어 부트캠프] 3기 코딩테스트 후기 / 7문제 / 문제 이슈 (0) | 2023.11.20 |
---|---|
[구름 플랫폼] 2023 현대자동차 부트캠프 3기 코딩테스트 예제 풀이 (0) | 2023.11.18 |
[소프티어] JAVA LV2 "바이러스" 풀이법 (0) | 2023.11.06 |
[소프티어] c++ LV2 "금고 털이" 풀이법 (0) | 2023.11.03 |
[소프티어] c++ LV3 "징검다리" 계수정렬 이용 풀이법 (0) | 2023.11.02 |