채점 방식 :
입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.
또한 제한시간이 1초이며 최대 256MB이라는 메모리 제한이 있다.
종류 1 : K ≤ 10
종류 2 : K ≤ 1000
종류 3 : 추가적인 제한 조건이 없음
종류 1은 수월하게 통과되는데 종류 2 조건에서 런 타임 에러 혹은 메모리 제한 초과가 떠서
DP 메모이제이션이나 반복문으로 바꿀라고 노력했는데 잘 안되는 것 같습니다..
아래 전체 코드입니다.
k가 조금만 높아지면 나오는 메모리 사용량이 계속 올라가는데..아직 배운지 얼마 안되서 잘 모르겠습니다..
def z(K, X):
dp = [[0] * (K + 1) for _ in range(1 << K)]
for x in range(1, 1 << K):
dp[x][0] = float('inf')
for k in range(1, K + 1):
for x in range(1, 1 << K):
if dp[x][k] == 0:
next_x_1 = (x + 1) & ((1 << K) - 1)
next_x_2 = (x << 1) & ((1 << K) - 1)
dp[x][k] = min(1 + dp[next_x_1][k - 1], 1 + dp[next_x_2][k - 1])
return dp[int(X, 2)][K]
K = int(input())
X = input()
print(z(K, X))
