[SWEA] 9700. USB 꽂기의 미스터리

[SWEA] 9700. USB 꽂기의 미스터리

SW Expert Academy

** UPDATED!! 

 

문제를 풀었다. 내가 바보였다.

 

USB의 방향은 첫 시행 시에만 결정된다. 이후에는 이전 방향의 반대로 뒤집는 시행밖에 없다.

따라서, 방향의 확률 p는 일부 시행에서만 계산에 포함된다.

s2 = 처음에 맞는 방향으로 꽂았고, 정상적으로 꽂히지 않은 경우 = (p * (1 - q)) * 1 * (p * q)

위 경우에 한 번 뒤집었을 때는 역방향이므로 꽂히지 않는 확률밖에 없다. 나머지 계산은 이전과 같다.

 

마지막 정상적으로 꽂히는 경우는 어차피 소거될 부분이라서 생략했다.

상태 그래프를 그려놓고 생각했더니 이 그림에 매몰돼서 방향이 바뀌는 게 이미 결정된 사항이라는 걸 생각하지 못했다.

이 부분은 확실히 맞다고 생각하는 것도 다시 생각해 봐야겠다.

 

아래는 이전에 생각했던 잘못된 풀이.

---

 

다음 문제!

 

라고 골라놨는데, 문제가 당췌 무슨 내용인지 이해가 되지 않는다.

각 테스트케이스는 USB를 맞는 방향으로 꽂을 확률 p와, USB가 정상적으로 꽂힐 확률 q가 주어진다.

즉, 맞는 방향으로 꽂았지만 정상적으로 인식이 안 될 가능성(1-q)이 있음을 의미한다. 물론 USB를 맞지 않는 방향으로 꽂았다면 USB는 정상적으로 꽂히지 않는다.

USB가 정상적으로 꽂히지 않을 경우, 무조건 USB 방향을 뒤집어서 다시 시도한다.

 

USB를 한 번 뒤집어서 정상적으로 꽂을 확률을 s1, 두 번 뒤집어서 정상적으로 꽂을 확률을 s2라고 했을 때

주어진 p와 q에 따라 s1 < s2 가 성립하는지를 YES/NO로 출력하는 문제이다.

 

내가 이해한 바로는, 이 시행에는 세 가지 상태가 존재한다.

1. 맞는 방향으로 꽂았고, 정상적으로 꽂혔다. (p * q)

2. 맞는 방향으로 꽂았고, 정상적으로 꽂히지 않았다. (p * (1 - q))

3. 맞는 방향으로 꽂지 않았다. (1-p)

 

이런 식으로

 

시행의 결과가 상태 1일 경우, 바로 종료된다. 첫 시행이 1일 경우 뒤집기는 발생하지 않는다.

시행의 결과가 상태 3일 경우, 다음 상태는 1 또는 2가 된다. 

시행의 결과가 상태 2일 경우, 다음 상태는 3이 되고, 그 다음 상태는 1 또는 2가 된다. 상태 2는 최소 2회의 뒤집기 시행을 보장한다.

 

즉, 이 문제에서 의미하는 s1, s2는 다음의 경우를 의미한다.

s1 = 처음에 반대 방향으로 꽂았을 경우 = 첫 시행이 상태 3이고 그 다음 시행이 상태 1인 경우 = (1 - p) * (p * q)

s2 = 처음에 맞는 방향으로 꽂았고, 정상적으로 꽂히지 않은 경우 = 첫 시행이 상태 2이고, 그 다음 상태 3 -> 상태 1 = (p * (1 - q)) * (1 - p) * (p * q)

 

그런데 이대로 s1, s2를 계산할 경우 주어진 첫 번째 테스트 케이스는

p = 0.8, q = 0.5

s1 = 0.2 * 0.8 * 0.5 = 0.08

s2 = 0.8 * 0.5 * 0.2 * 0.8 * 0.5 = 0.032

 

대충 봐도 s1이 크다. 하지만 답은 YES, s1 < s2가 성립한다 이다.

 

새로 게시된 문제인데도 20명이 풀었고, 정답률도 높으니 문제 자체가 잘못된 건 아닌 것 같은데. 왜 계산이 틀린지 모르겠다.

누군가도 나와 같은 생각을 한 것 같다. 차이점이 있다면 이 사람은 결국 풀었고 나는 못 풀었지.

 

p.s. 글 써 놓고 읽으면서 찬찬히 생각해 봤는데 p랑 q가 독립시행이 아니라고 생각하면 p * q가 아니겠구나 싶다. (심한 욕) ...근데 그렇다 쳐도 저 세 개의 상태로 돌아가는 한 s2가 절대 더 커질 수가 없다. 같다면 모를까.. 상태1,2,3이 각각 q, 1-q, 1-p라고 생각해도 달라질 건 없다.

앞의 결과가 뒤에 올 확률에 영향을 미치니까 곱해야 되는 거 맞잖아...?