[BOJ 20952, Python 3] 게임 개발자 승희

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

20952번: 게임 개발자 승희

1e9 + 7을 써야 하는 걸 10e9 + 7로 써두고, 알고리즘이 틀린 줄 알고 엄청 헤맸다 😭😭

 

풀이

N = M = 100,000이므로 하나하나씩 비교하는 O(N^2)는 돌아가지 않는 것은 당연합니다. 그래서 좀 더 빠르게 계산을 할 수 있는 방법을 찾아야 하는데, 문제에서 B[i]를 더하다가 7의 배수 원소가 나오면 삭제한다고 했으므로 7로 만들 수 있는 나머지인 0, 1, 2, 3, 4, 5, 6을 이용하여 수열 B의 원소를 하나씩 더하면 O(7 * N)으로 획기적으로 시간을 줄일 수 있음을 알 수 있습니다.

 

그다음 문제에서 어떤 연산이 현재 남아있는 모든 원소를 삭제하는 경우에는 해당 연산을 수행하지 않는다고 나와있으므로 나머지가 k인 원소들의 개수를 저장한 count 배열을 만들고, 윗 문단의 알고리즘을 수행할 때 count배열을 복사한 new_count 배열을 하나 만들어 줍니다. 그 후에는 B[i]를 더해서 나머지가 0이 되는 값 x를 찾아 new_count[x] = 0으로 해줍니다. 연산이 다 끝나고 나서 마지막에 sum(new_count) != 0이면 count = new_count를 해주고, sum(new_count) == 0이면 해당 연산은 업데이트를 하지 않고 넘어가주면 됩니다.

 

코드에서는 new_count뿐만 아니라 이미 7의 배수가 된 적이 있는지 확인하는 zero와 new_zero 배열, B[i]를 더한 값을 업데이트하면 val과 new_val 배열도 있습니다.

 

코드

input = __import__('sys').stdin.readline
MOD = 10**9 + 7
n, m = map(int, input().split())
A = [*map(int, input().split())]
B = [*map(int, input().split())]
val = [i for i in range(7)]
zero = [False] * 7
count = [0] * 7
for i in range(n): count[A[i] % 7] += 1
plus = 0
for i in range(m):
    new_val = val.copy()
    new_count = count.copy()
    new_zero = zero.copy()
    for j in range(7):
        if zero[j]: continue
        new_val[j] = (val[j] + B[i]) % 7
        if new_val[j] == 0:
            new_count[j] = 0
            new_zero[j] = True
    if sum(new_count) != 0:
        plus = (plus + B[i]) % MOD
        val, count, zero = new_val, new_count, new_zero
ans = [(A[i] + plus) % MOD for i in range(n) if not zero[A[i] % 7]]
print(len(ans))
print(*ans)