분할 정복을 이용한 거듭제곱2 [백준] 15824: 너 봄에는 캡사이신이 맛있단다 - JAVA https://www.acmicpc.net/problem/15824 풀이매운 정도를 배열로 입력받아 몇 개를 선택하여 조합을 만들 경우 그 안에서 최댓값과 최솟값의 차이가 그 조합의 맛의 정도가 된다. 이런 맛의 정도들의 합을 구하는 문제이다. 먼저 입력받은 배열을 정렬했다. i번째 인덱스의 경우 이 값이 최솟값이 되는 경우는 2^i개의 경우, 이 값이 최댓값이 되는 경우는 2^(N - i - 1)개의 경우가 된다. 2의 거듭제곱을 구하기 위해 분할정복을 이용했다. 메모리: 58472KB시간: 792ms언어: Java 11import java.util.*;import java.io.*;public class Main { static final int MOD = 1_000_000_007; st.. 2024. 5. 16. [백준] 12850: 본대 산책2 - JAVA https://www.acmicpc.net/problem/12850 풀이결론부터 말하면 분할정복을 통해 행렬의 거듭제곱을 하는 문제였다. 각각의 포인트에서 연결된 길을 이차원배열에 저장했다. 초기 배열을 V1이라고 하면 V1[a][b]는 a에서 b로 1분만에 갈 수 있는 경로의 수를 의미한다. V1을 제곱한 것을 V2라고 하면 V2[a][b]는 a에서 b로 2분만에 갈 수 있는 경우의 수이다. 즉, Vx[a][b]는 a에서 b로 x분만에 갈 수 있는 경우의 수를 의미한다. 따라서 주어진 D만큼 V행렬을 제곱하여 V[0][0]을 구하면 D분만에 0에서 0으로 갈 수 있는 경우의 수이다. 분할정복은 doPow함수로 구현했고, 행렬의 곱셈은 multiply함수로 구현했다. 메모리: 14256KB시간: 124.. 2024. 5. 12. 이전 1 다음