https://codeforces.com/contest/1553/problem/C
시간 3초, 메모리 256MB
input :
output :
조건 :
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)
아쉬운 문제다. 너무 ?를 어떻게 하는지만 생각하다가 굳어버린 나를 반성하며 메모장에다가 써두던지 해야겠다...