[ 백준 6426 ] Pseudo-Random Numbers

1. 문제: https://www.acmicpc.net/problem/6426

6426번: Psuedo-Random Numbers

 

2. 풀이

문제를 간단하게 해석하면 다음과 같다. 

 

컴퓨터는 실제로 난수를 발생시킬 수 없지만, 유사난수 생성기(pseudo-random numbers generator)를 통해 난수를 만들어내는 것 처럼 할 수 있다. 널리 알려진 난수 생성에 사용되는 기술 중 하나로는 '선형 합동 생성기(Linear Congruential Generator, LCG)'가 있다. 선형 합동 생성기는 곱함수(Z), 더함수(I), 나눔수(M)으로 구성된다. 시작점을 L 이라고 했을 때 다음 인자는 아래의 공식을 통해 생성된다.
L = (Z * L + I) mod M
선형 합동 생성기는 나눔수인 M을 난수의 최대 주기로 갖게 된다. Z, I, M, L이 주어질 때, 난수 생성기의 주기를 출력하라.

 

문제에서 주어진 정보 외에 위키를 찾아보니, 선형 합동 생성기의 경우 난수의 주기가 정해져있고, 마지막으로 생성된 난수를 알면 그 다음부터는 예측이 가능하기 때문에 암호학적으로 안전한 유사난수 생성기는 아니라고 한다.

 

이 문제의 중점은 주기의 시작점이 문제에서 주어진 L이 아니란 것이다. 우리가 발생시킬 난수의 시작점은 L이지만 주기의 시작점은 L이 아니란 얘기다.

 

이에, 수를 변환시키면서 L로 돌아올 때까지 루프를 돌릴 경우 무한루프에 빠질 수 있기 때문에, HashSet을 사용해 더 이상 사이즈가 증가하지 않을 때까지 반복하는 것으로 풀이하였다.

 

3. 코드

public class PseudoRandomNumber {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String s = null;
		int idx = 0;
		while(!(s = br.readLine()).equals("0 0 0 0")) {
			StringTokenizer st = new StringTokenizer(s);
			int Z = Integer.parseInt(st.nextToken());
			int I = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int L = Integer.parseInt(st.nextToken());
			HashSet<Integer> set = new HashSet<Integer>();
			while(true) {
				L = (Z * L + I)%M;
				int size = set.size();
				set.add(L);
				if(size == set.size())
					break;
			}
			bw.write(String.format("Case %d: %d\n", ++idx, set.size()));
		}
		bw.flush();
		bw.close();
		br.close();
	}

}

 

4. Reference

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%98%95_%ED%95%A9%EB%8F%99_%EC%83%9D%EC%84%B1%EA%B8%B0

선형 합동 생성기 - 위키백과, 우리 모두의 백과사전