Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
반응형
문제
10830번: 행렬 제곱
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
풀이
행렬 A의 제곱 수인 B는 최대 100,000,000,000의 값을 가지기 때문에 단순히 A를 반복해 곱하는 것은 시간 초과를 발생시킨다. 이와 같이 입력값이 너무 큰 경우 분할 정복을 떠올리자.
제곱 수를 pow_num이라고 하면
pow_num %2 ==1 인 경우, 즉 홀수라면 A^(pow_num-1) * A를
짝수라면 A^(pow_num/2) * A^(pow_num/2) 로 계산한다면 제곱 연산을 O(logB) 수준으로 줄일 수 있다.
단 해당 문제는 B의 최댓값이 int형의 최댓값을 벗어나므로 long long형으로 선언해야하고
본인의 경우 원소 값이 한 개라도 1,000이고 B가 1인 경우 1,000으로 나눈 값을 출력하는 예외를 처리하지 못하여 고생했다.
최종적으로 값을 출력할 때도 나누기 연산을 해주자!
코드
반응형
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.1149 - RGB거리 (C++) (0) | 2020.11.08 |
|---|---|
| [백준] No.2170 - 선 긋기(C++) (0) | 2020.11.07 |
| [백준] No.1780 - 종이의 개수 (C++) (0) | 2020.10.30 |
| [백준] No.17136 - 색종이 붙이기 (C++) (0) | 2020.10.29 |
| [백준] No.1543 - 문서 검색 (C++) (0) | 2020.10.26 |
댓글