모듈러연산2 백준 10830번 : 행렬 제곱 | JAVA 📌 알고리즘 선택 이 문제는 단순히 하나의 행렬을 계속해서 곱해나가는 문제이지만, 그렇다고 행렬을 곱하는 연산만 구현한다면,, 시간초과가 날 것이다. 그렇기에 거듭제곱의 지수를 반으로 나누어가며 분할정복(dp)해야 효율적으로 연산할 수 있다. 지수를 반으로 나누는 형식의 분할정복 풀이법은 앞선 문제 '백준 11401번 이항계수 3'에서 구현한 적이 있기에 더욱 쉽게 문제를 해결할 수 있었다. 📌 풀이 전체적인 구현 흐름은 다음과 같다. main() 1. 행렬의 크기 N과 지수 값 B 입력받기 - (주의) 문제에서 B 값의 범위가 1 ≤ B ≤ 100,000,000,000 이므로, B의 타입에 유의해야 한다. - B의 타입을 long으로 하자. 2. 2차원의 행렬 입력받기 - pow 함수에서 지수가 1인 .. 2023. 3. 14. 백준 11401번 : 이항 계수 3 | JAVA 📌 알고리즘 선택 이항 계수를 구하기 위해서는 팩토리얼을 주로 사용해야 하는데, 팩토리얼을 풀기 위해서는 DP를 사용하여 계산 횟수를 줄이는 것이 가장 효율적이라고 생각했다. 다만, 주의해야 할 점은 입력값의 범위이다. 20!만 되어도 이미 long 범위를 넘어서기 때문에 수를 작게 만들 방법을 생각해내야 한다. 📌 풀이 이 문제를 풀기 위해서는, 즉 수를 작게 만들기 위해서는, 모듈러 연산과 페르마의 소정리를 알고 있어야 한다. 모듈러 연산에서 나눗셈은 없기에, 역원을 이용해 나눗셈을 곱셈으로 변환시켜야 한다. 이에 대해 간략히 식으로 적어보았다. 📌 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStr.. 2023. 3. 13. 이전 1 다음
