[BOJ] 20410번: 추첨상 사수 대작전! (Easy)

https://www.acmicpc.net/problem/20410

 

---

문제

APC는 매년 교내 참가자들에게 추첨상을 지급하고 있다. 올해 추첨상은 공정한 추첨을 위해 준표가 직접 작성한 난수생성기를 통해 추첨을 하고자 한다. 난수생성기란, 이론적으로 예측을 더 할 수 없도록 일련의 숫자나 심볼을 생성하는 장치이다.

주헌 : 형이 짠 난수생성기가 공정하다는 걸 어떻게 알아 ?

준표 : 걱정 마! c언어에서 ANSI 표준으로 사용하는 '선형합동법(Linear Congruential)' 을 구현할 거니까 ~

주헌 : 선형합동법이 뭔데 ?

준표 : 그게 뭐냐면 ..

준표의 설명을 간단히 정리해보면,

X1 = (a × Seed + c) % m

X2 = (a × X1 + c) % m

...

Xn + 1 = (a × Xn + c) % m

이런 식으로 준표가 몰래 정하는 a, c, m 와 참가자들이 정하는 Seed 값을 바탕으로 위 공식에 따라 난수를 생성한다는 것이었다.

주헌 : 음... a, c, m을 아무렇게나 잡으면 안 되지 않을까 ?

준표 : 응. Hull-Dobell 정리에 따르면 그게 맞아. 그런데 귀찮아서 그냥 m을 대충 내가 좋아하는 소수로 하려구.

주헌 : (형이 좋아하는 소수..? 씨익..)

사실 주헌이는 올해에는 추첨상을 반드시 받아내겠다는 야망이 있었다! 위 대화는 그를 위한 초석이었던 것이다! 주헌이는 준표를 너무 잘 알기 때문에 준표가 좋아하는 소수를 이미 알고 있었고, 준표가 자신이 직접 작성한 난수생성기에 문제가 없음을 참가자들에게 알려주기 위해 실제 추첨 전 난수생성기가 잘 작동한다는 것을 모두의 앞에서 시연하기로 되어있었다.

주헌이는 계략을 짰다. 주헌이는 시연 중 참가자들이 정한 Seed와 이를 이용해 만들어진 X1, X2 를 이용해 준표가 몰래 정한 a, c를 찾아낼 것이다. 만약 주헌이가 추첨상을 받지 못한다면, 찾아낸 a, c를 폭로해 모든 것이 조작되었다고 주장하며 추첨 자체를 무효로 만들 계략이다! 주헌이는 a, c를 자동으로 찾아주는 프로그램을 만들고자 한다.

 

풀이

앞서 풀었던 백준 19532번(https://haerxeong.tistory.com/4)과 유사한 방식으로 풀고자 하였다.

그러나 왜 틀렸는지 조차 모르겠는... 이럴 때가 정말 디버깅하기 막막한 것 같다.

m, seed, x1, x2 = map(int, input().split())
flag = False
for a in range(m):
    for c in range(m):
        if x1 == (a * seed + c) % m and x2 == (a + x1 + c) % m:
            flag = True
            break
    if flag: break
print(a, c)

 

알고보니 x2 == a * x1 ~ 이어야 하는데 a + x1으로 썼다. 아주 한심한 실수......

 

m, seed, x1, x2 = map(int, input().split())
flag = False
for a in range(m):
    for c in range(m):
        if x1 == (a * seed + c) % m and x2 == (a * x1 + c) % m:
            flag = True
            break
    if flag: break
print(a, c)

 

성공! :0