Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 정수론
- 정렬
- 분할 정복
- 구현
- ifnull
- 브루트포스
- toUpperCase()
- 공간 복잡도
- 스택
- 시간 복잡도
- 거듭제곱
- 그리디 알고리즘
- toLowerCase()
- 문자열
- 자료 구조
- 그래프 이론
- BFS
- 연결 리스트
- 요세푸스 문제
- 배열
- ListIterator
- 큐
- 빅오 표기법
- 소수 판정
- IS NOT NULL
- 너비 우선 탐색
- MySQL
- 백트래킹
- 수학
- 그래프 탐색
Archives
- Today
- Total
배푸니까
[백준 / JAVA] 1629. 곱셈 본문
반응형
https://www.acmicpc.net/problem/1629
1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
💻 풀이 결과
💯 최종 코드
import java.util.Scanner;
public class Main {
// pow 함수
public static long pow(int a, int b, int c) {
// base condition
if (b == 1) {
return a % c;
}
long res = pow(a, b / 2, c);
res = res * res % c;
// b가 짝수일 때
if (b % 2 == 0) {
return res;
}
// b가 홀수일 때
else {
return res * a % c;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int A = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();
System.out.println(pow(A, B, C));
}
}
💢 틀린 이유
- 분할 정복 기법을 쓰지 않아서 시간초과가 발생하였다.
💬 풀이 과정
- 절반으로 계속 나눠간다고 생각해야 한다.
- 짝수일 때는 그대로 res를 반환하면 되고, 홀수일 때는 a를 한번 더 곱해야 한다.
💡 깨달은 점
1. 분할 정복 기법
- 분할하여 재귀적으로 문제를 해결하는 방법이다.
- 이 문제에서 절반을 제곱하는 개념으로 생각해 보면 된다.
반응형
'백준' 카테고리의 다른 글
[백준 / JAVA] 15649. N과 M (1) (1) | 2023.10.22 |
---|---|
[백준 / JAVA] 2146. 다리 만들기 (0) | 2023.10.16 |
[백준 / JAVA] 13549. 숨바꼭질3 (0) | 2023.09.03 |
[백준 / JAVA] 2573. 빙산 (0) | 2023.08.31 |
[백준 / JAVA] 2206. 벽 부수고 이동하기 (0) | 2023.08.30 |