[백준/파이썬][Silver III] Password Problem (Large) - 12395

[Silver III] Password Problem (Large) - 12395

문제 링크

성능 요약

메모리: 143524 KB, 시간: 180 ms

분류

브루트포스 알고리즘, 수학, 확률론

제출 일자

2025년 2월 13일 18:46:10

문제 설명

I have a really long password, and sometimes I make a mistake when I type it. Right now I've typed part of my password, but I might have made some mistakes. In particular, I might have pressed the wrong key while typing one or more of the previous characters. Given how likely I was to get each character right, what should I do?

I have three options:

1. Finish typing the password, then press "enter". I know I'll type the rest of the characters perfectly. If it turns out that one of the earlier characters was wrong, I'll have to retype the whole thing and hit "enter" again -- but I know I'll get it right the second time.
2. Hit "backspace" some number of times, deleting the last character(s) I typed, and then complete the password and press "enter" as in option 1. If one of the characters I didn't delete was wrong, I'll have to retype the whole thing and press "enter", knowing I'll get it right the second time.
3. Give up by pressing "enter", retyping the password from the start, and pressing "enter" again. I know I'll get it right this time.

 

I want to minimize the expected number of keystrokes needed. Each character in the password costs 1 keystroke; each "backspace" costs 1 keystroke; pressing "enter" to complete an attempt or to give up costs 1 keystroke.

Note: The "expected" number of keystrokes is the average number of keystrokes that would be needed if the same situation occurred a very large number of times. See the example below.

Example

Suppose my password is "guest" and I have already typed the first two characters, but I had a 40% chance of making a mistake when typing each of them. Then there are four cases:

• I typed "gu" without error. This occurs with probability 0.6 * 0.6 = 0.36.
• I typed the 'g' correctly but I made a mistake typing the 'u'. Then I have two letters typed still, but the second one is wrong: "gX". (Here, the 'X' character represents a mistyped letter.) This occurs with probability 0.6 * 0.4 = 0.24.
• I typed the 'u' correctly but I made a mistake typing the 'g': "Xu". This occurs with probability 0.4 * 0.6 = 0.24.
• I made a mistake typing both letters, so I have two incorrect letters: "XX". This occurs with probability 0.4 * 0.4 = 0.16.

 

I don't know how many mistakes I actually made, but for any strategy, I can calculate the expected number of keys required to use it. This is shown in the table below:

 

	"gu"	"gX"	"Xu"	"XX"	Expected
Probability	0.36	0.24	0.24	0.16	-
Keystrokes if I keep typing	4	10	10	10	7.84
Keystrokes if I press backspace once	6	6	12	12	8.4
Keystrokes if I press backspace twice	8	8	8	8	8
Keystrokes if I press enter right away	7	7	7	7	7

 

If I keep typing, then there is an 0.36 probability that I will need 4 keystrokes, and an 0.64 probability that I will need 10 keystrokes. If I repeated the trial many times, then I would use 4 keystrokes 36% of the time, and 10 keystrokes the remaining 64% of the time, so the average number of keystrokes needed would be 0.36 * 4 + 0.64 * 10 = 7.84. In this case however, it is better to just press enter right away, which requires 7 keystrokes.

입력

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing two integers, A and B. A is the number of characters that I have already typed, and B is the total number of characters in my password.

This is followed by a line containing A real numbers: p₁, p₂, ..., p_A. p_i represents the probability that I correctly typed the i^th letter in my password. These real numbers will consist of decimal digits and at most one decimal point. The decimal point will never be the first or the last character in a number.

Limits

• 1 ≤ T ≤ 20.
• 0 ≤ p_i ≤ 1 for all i.
• 1 ≤ A ≤ 99999.
• A < B ≤ 100000.

출력

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the expected number of additional keystrokes I need, not counting the letters I have typed so far, and assuming I choose the optimal strategy. y must be correct to within an absolute or relative error of 10^-6.

풀이

def sol_12395() :
    A, B = map(int, input().split())
    already_key = list(map(float, input().split()))
    p = [1.0]

    for i in range(A) :
        p.append(p[-1] * already_key[i])
    
    res = 1 << 32

    for k in range(A + 1) :
        cnt = k + (B - A + k + 1) + (1-p[A-k]) * (B + 1) 

        res = min(res, cnt)

    res = min(res, 1 + B + 1)

    return res

T = int(input())
for t in range(1, T + 1) :
    print(f"Case #{t}: {sol_12395():.6f}")

테스트 케이스 1: $A=2$, $B=5$, 확률: 0.6, 0.6

상황 정리

• 이미 입력한 문자: 2개
• 전체 문자: 5개 → 남은 문자는 $ 5 - 2 = 3 $ 개
• 각 문자가 올바를 확률:
  • 1번째: 0.6
  • 2번째: 0.6
• 전체가 맞을 확률:
  $$ 0.6 \times 0.6 = 0.36 $$

옵션별 전략

1. 계속 입력하기 (Keep Typing):
   • 정상인 경우:
     남은 3개 문자를 정확히 입력하고 엔터 → $ 3 + 1 = 4 $ 키
   • 오타가 있을 경우:
     남은 3개 + 엔터(4키) 후, 비밀번호 전체 5개와 엔터 다시 입력 → $ 4 + (5 + 1) = 10 $ 키
   • 기대 키 수:
     $$ 0.36 \times 4 + 0.64 \times 10 = 1.44 + 6.4 = 7.84 $$
     
     
2. 백스페이스 사용하기 (Backspace):
   • 예를 들어, 백스페이스 1번 $(K = 1)$를 선택하면:
     • 남겨지는 문자는 $A - K = 2 - 1 = 1$ 개
     • 첫 글자가 맞을 확률은 0.6
     • 정상인 경우:
       비용 = 백스페이스 1번 + 남은 1개 문자를 재입력하고, 그 후 남은 $ 5 - (2 - 1) = 4 $ 개
       문자를 입력 + 엔터
       → $ 1 + 4 + 1 = 6 $ 키
     • 오타가 있을 경우:
       위 6키에 더해 전체 재입력 $ 5 + 1 = 6$ 키 → $ 6 + 6 = 12 $ 키
     • 기대 키 수:  
       $$ 0.6 \times 6 + 0.4 \times 12 = 3.6 + 4.8 = 8.4 $$
       
   • 백스페이스 2번$(K=2)$의 경우:
     • 남겨지는 문자는 $ 2 - 2 = 0 $ 개 (즉, 아무것도 남지 않으므로 확률 1로 취급)
     • 비용 = $2(백스페이스) + 5 - 0 = 5$ (전체 문자 입력) + 엔터 1 → $ 2 + 5 + 1 = 8 $ 키
     • 기대 키 수: 8
3. 바로 포기하기 (Give Up):
   • 동작:
     지금 바로 엔터를 누른 후, 비밀번호 전체 5개와 엔터 재입력
   • 비용:
     $ 1 (엔터) + 5 + 1 = 6$ → 총 $ 7 $ 키

최적 선택

• 계속 입력: 7.84 키
• 백스페이스 1번: 8.4 키
• 백스페이스 2번: 8 키
• 바로 포기: 7 키

따라서 최적 전략은 바로 포기하기이며, 기대 추가 키 수는 7.000000회.

---

테스트 케이스 2: $A=1$, $B=20$, 확률: 1

상황 정리

• 이미 입력한 문자: 1개
• 전체 문자: 20개 → 남은 문자는 $ 20 - 1 = 19 $ 개
• 입력한 문자는 확실히 맞음 $ (p_{1} = 1) $

옵션별 전략

1. 계속 입력하기:
   • 남은 19개 문자와 엔터 → $ 19 + 1 = 20 $ 키
   • 오타 발생 확률이 0이므로 재입력 없음
   • 기대 키 수: 20
2. 백스페이스 사용하기:
   • 예를 들어, 백스페이스 1번을 누르면:
     • 남겨지는 문자는 $ 1 - 1 = 0 $ 개
     • 비용 = 1(백스페이스) + $20 - 20 = 20$ (전체 문자 입력) + 엔터 1 → $ 1 + 20 + 1 = 22 $ 키
   • 다른 백스페이스 옵션도 더 많은 키를 요구함
3. 바로 포기하기:
   • 비용 = 엔터 1 + 전체 비밀번호 20개와 엔터 1 → $ 1 + 21 = 22 $ 키

최적 선택

• 계속 입력: 20 키
• 백스페이스나 포기: 22 키 이상

따라서 최적 전략은 계속 입력하기이며, 기대 추가 키 수는 20.000000회.

---

테스트 케이스 3: $A=3$, $B=4$, 확률: 1, 0.9, 0.1

상황 정리

• 이미 입력한 문자: 3개
• 전체 문자: 4개 → 남은 문자는 $ 4 - 3 = 1 $ 개
• 각 문자 올바를 확률:
  • 1번째: 1
  • 2번째: 0.9
  • 3번째: 0.1
• 전체가 맞을 확률: $ 1 \times 0.9 \times 0.1 = 0.09 $

옵션별 전략

1. 계속 입력하기:
   • 정상인 경우:
     남은 1개 문자와 엔터 → $ 1 + 1 = 2 $ 키
   • 오타가 있을 경우:
     $2$ 키 사용 후, 전체 비밀번호 4개와 엔터(5키) 재입력 → $ 2 + 5 = 7 $ 키
   • 기대 키 수:
     $$0.09 \times 2 + 0.91 \times 7 = 0.18 + 6.37 = 6.55$$
2. 백스페이스 사용하기:
   • 백스페이스 1번 ($K=1$):
     • 남겨지는 문자는 $ A - K = 3 - 1 = 2 $ 개
     • 이때 남은 두 문자(1번째와 2번째)가 모두 맞을 확률은 $1 \times 0.9 = 0.9$
     • 정상인 경우:
       비용 = 1(백스페이스) + 입력해야 하는 문자 수:
       재입력한 1글자(백스페이스한 문자)와 남은 $ B - (A - K) = 4 - 2 = 2 $ 글자, 그리고 엔터
       → $ 1 + (1 + 2) + 1 = 1 + 3 + 1 = 5 $ 키
       (※ 문제 설명의 예제에서는 6키로 계산했으나 여기서 재계산하면:
       백스페이스 1번 → 비용 = 백스페이스 $1 + (4 - (3-1) + 1) = 1 + (4-2+1)=1+3=4$.
       다만, 위 문제 설명 예제에서는 6키로 되어 있으므로 다시 확인해 보겠습니다.)
       • 오타가 있을 경우:
         위 4키에 더해 전체 비밀번호 재입력 $B+1=5$ 키
         → $4 + 5 = 9$ 키
       • 기대 키 수:
         $$0.9 \times 4 + 0.1 \times 9 = 3.6 + 0.9 = 4.5$$
     • 정확한 계산:
       백스페이스 $K$번을 할 경우, 남은 확신하는 문자는 $A-K$개이므로
       추가로 입력할 키 = $K$ (백스페이스) + $[B - (A - K)]$(재입력해야 할 문자들) + $1$ (엔터)
       여기서 $K=1$ 이면,
       추가 키 = $1 + [4 - (3-1)] + 1 = 1 + [4-2] + 1 = 1 + 2 + 1 = 4 $ 키
       • 오타가 있을 경우:
         위 4키에 더해 전체 비밀번호 재입력 $B+1=5$ 키
         → $4 + 5 = 9$ 키
       • 기대 키 수:
         $$0.9 \times 4 + 0.1 \times 9 = 3.6 + 0.9 = 4.5 $$
   • 백스페이스 2번 ($K=2$):
     • 남겨지는 문자는 $3-2=1$개→ 첫 문자는 1 (확실히 맞음)
     • 추가 키 = $2$ (백스페이스) + $[4 - (3-2)] + 1 = 2 + [4 - 1] + 1 = 2+3+1 = 6$ 키
     • 오타 발생 확률 0 → 기대 키 수 = 6
   • 백스페이스 3번 ($K=3$):
     • 남겨지는 문자는 0개
     • 추가 키 = $3$ (백스페이스) + $[4 - 0] + 1 = 3 + 4 + 1 = 8$ 키
     • 기대 키 수 = 8
3. 바로 포기하기 (Give Up):
   • 비용 = 엔터 1 + 전체 비밀번호 4개와 엔터 1 → $1 + 5 = 6$ 키

최적 선택

• 계속 입력: 6.55 키
• 백스페이스 1번: 4.5 키
• 백스페이스 2번: 6 키
• 백스페이스 3번: 8 키
• 포기하기: 6 키

따라서 최적 전략은 백스페이스 1번이며, 기대 추가 키 수는 4.500000회.

 

처음에는 시간 초과가 나오게 풀었더니, 챗GPT와 함께 풀어낼 수 있었다. 

문제 자체도 영어로 되어있다보니, 많이 헷갈렸는데 수식을 하나하나 읽고 구현하다보니 쉽게 풀어날 수 있었다. 

수학적인 공부도 필요하다는 생각이 들었다.