https://codeforces.com/contest/1553/problem/C
시간 3초, 메모리 256MB

input :

• t (1 ≤ t ≤ 1000)
• one line containing the string s, consisting of exactly 10 characters

output :

• For each test case, print one integer — the minimum possible number of kicks in the penalty phase.

조건 :

• if si is 1, then the i-th kick will definitely score a goal;
  if si is 0, then the i-th kick definitely won't score a goal;
  if si is ?, then the i-th kick could go either way.
  1이라면 득점을 하고, 0이라면 득점을 못한다. ?인 경우에는 원하는대로 선택할 수 있다.

• Based on your predictions, you have to calculate the minimum possible number of kicks there can be in the penalty phase
  페널티킥을 차는 선수가 가장 적은 상황을 예측하시오.

---

문제를 해결할 때 알고리즘의 변동이 많아 코드를 계속 바꾸다 보니 더 이상 의지가 없었었다.
2가지 문제가 있었는데
1. ?를 어떻게 해결할까
2. 승패를 결정난 것을 어떻게 알아야 하는가

?

사실 입력받은 문자열의 길이는 10밖에 안 된다. 이 말은 ?를 선택할 수 있는 모든 경우의 수를 따졌을 때 문자열이 ?로만 이루어져 있다면 이 때 가능한 경우는 2^10 1024개 밖에 되지 않는다.
그래서 완전탐색을 할까 아니면 재귀를 하는게 편할까 고민하다가 결국 2진수를 사용하기로 결정했다.

승패

그러면 승패를 따져야 하는데... 이 때 득점차가 3점이상이 나는 경우밖에 생각을 하지 않았다...
현재까지 4번째 키커까지 왔는데 결과가 3 : 1이면 승부가 난 것으로 이런 것들도 판단을 해야한다.

왜 승부가 났다고 보는 것일까? 더 이상 남은 키커가 모두 득점을 해도 승패를 뒤집을 수 없기 때문이다. 결국 그냥 남은 키커가 다 넣는다는 가정하에 두 팀의 점수를 계속 비교하면 되는 것이다.

선축

여기서 하나 더 승부차기는 차는 순서가 존재한다. 먼저 차는 사람의 경우와 나중에 차는 사람의 기준으로 남은 키커를 계산하는 방식이 다르다. 왜냐하면 1명의 차이가 존재하기 때문이다. 선축을 한 사람 기준에서 그 뒤에 차는 사람이 존재해서 이 배열 길이를 그대로 사용한다면 이를 주의 해야한다.

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    data = sys.stdin.readline().rstrip()
    temp = []
    cnt, ans = 0, 10

    for item in data:
        if item == '?':
            cnt += 1
        temp.append(item)

    for i in range(2 ** cnt):
        team = [0, 0]
        q = bin(i)[2:]

        question_idx = 0
        pre = ""
        for j in range(len(q), cnt):
            pre += "0"

        q = pre + q
        for idx in range(len(data)):
            if data[idx] == '?':
                temp[idx] = q[question_idx]
                question_idx += 1

            team[idx % 2] += int(temp[idx])

            if team[0] > team[1] + (len(data) - idx) // 2:
                ans = min(ans, idx + 1)

            if team[0] + (len(data) - 1 - idx) // 2 < team[1]:
                ans = min(ans, idx + 1)

    print(ans)

아쉬운 문제다. 너무 ?를 어떻게 하는지만 생각하다가 굳어버린 나를 반성하며 메모장에다가 써두던지 해야겠다...