문제링크: https://www.acmicpc.net/problem/26008
사용한 자료구조: 없음
마치 문제에서는 해시를 사용하도록 하는 것 같지만! 사실 그냥 mod연산 문제다! 수학문제다.
찾아낸 규칙
해시 값을 H, 배열의 원소를 P, 곱해지는 숫자를 A, mod 연산할 수를 M이라고 한다. 문제에서 주어진 해시 함수를 써보면 다음과 같다.
모듈러 연산을 M으로 하기 때문에 해시값은 0~(M-1)중의 하나로 무조건 나오게 된다. P배열을 어떤 수로 조합 하더라도 0~(M-1)의 값이 나오게 된다.
P는 0~(M-1) 중 하나이고 P는 n개 있으므로 M의 n제곱이다.
H는 0~(M-1) 중 하나가 되므로 M으로 나눠준다.
따라서 어떤 해시값이 가질 수 있는 P배열의 조합 개수는 다음과 같다.
코드 및 설명
모든 수를 입력 받고 m의 n-1제곱을 계산하기 위해 반복문을 작성했다.
문제에서 배열의 조합개수가 너무 많을 경우 때문에 10000000007로 나눈 값을 반환하라고 했다.
m의 n-1제곱의 수가 너무 클 경우 long자료형에 다 담지 못할 경우를 대비하여 m을 곱할때마다 1000000007로 나눠준다.
그리고 마지막에 한번 더 1000000007로 나누어 정답을 반환한다.
- 참고: 모듈로 연산의 곱셈법칙에 따라 연산한 것이다 : (A * B) mod C = (A mod C * B mod C) mod C
import java.util.Scanner;
public class Main {
public static void solution(int n, int m){
long result = 1;
for(int i = 0 ; i<n-1; i++){
result = (result * m) % 1000000007 ;
}
long ans = result % 1000000007;
System.out.println(ans);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n= sc.nextInt();
int m= sc.nextInt();
int a= sc.nextInt();
int h= sc.nextInt();
solution(n,m);
}
}시행 착오 및 교훈
일단 모듈러 연산을 전공 암호학 시간에 열심히 연습해둔 덕분이었는지 자료형 범위를 넘어서는 곱셈에서 나머지 연산을 해주는 부분에서는 막히지 않았다.(교수님 감사합니다..)
어떤 알고리즘 문제를 풀때 당장 어떤 자료구조에 어떻게 데이터를 처리할지 생각해 보는 것도 중요하지만 먼저 수학적으로 규칙을 찾아 수학적으로 풀어내는 것이 중요하다는 점을 한번 더 기억하게 되었다.
처음에 어떤 규칙을 찾아내려고 종이에 열심히 써서 규칙을 찾으려고 해봤지만 실패했다. 그리고 다시 몇번의 검색을 거쳐 수학적으로 풀어야 한다는 사실을 알게 되었다. 알고보니 그냥 확률 문제였던 것이다!
앞으로는 수학적 규칙을 찾아내는데도 신경을 써야겠다! 그럼 더 빨리 문제가 풀리는 경우가 많으니까!
