맞춰봐 1248번 백준 파이썬

문제:www.acmicpc.net/problem/1248

1248번: 맞춰봐

이 문제를 처음 접근했을 때 우선 N번째까지 해당하는 수열을 구하고 나머지의 수열을 확인하는 식의 코드를 작성했었다. 하지만 그것의 큰 문제점은 시간초과 문제였다. 시간초과 문제를 결국 해결하지 못해서 다른 분들의 코드를 참고하였다.

def ck(idx):
    hap = 0
    for i in range(idx, -1, -1):
        hap += result[i]
        if hap == 0 and S[i][idx] != 0:
            return False
        elif hap < 0 and S[i][idx] >= 0:
            return False
        elif hap > 0 and S[i][idx] <= 0:
            return False
    return True

def solve(idx):
    if idx == N:
        return True
    if S[idx][idx] == 0:
        result[idx] = 0
        return solve(idx+1)
    for i in range(1, 11):
        result[idx] = S[idx][idx] * i
        if ck(idx) and solve(idx+1):
            return True
    return False

N = int(input())
arr = list(input())
S = [[0]*N for i in range(N)]
for i in range(N):
    for j in range(i, N):
        temp = arr.pop(0)
        if temp == '+':
            S[i][j] = 1
        elif temp == '-':
            S[i][j] = -1

result = [0] * N
solve(0)
print(' '.join(map(str, result)))

 

참고:https://hazung.tistory.com/127

[알고리즘] 백준 1248 맞춰봐 / python, 백트랙킹

	0	1	2	3
0	-	+	0	+
1		+	+	+
2			-	-
3				+

해당 문제에서 주어진 첫번째 예시를 표로 표시하였다. 여기서 눈 여결 볼 것은 대각선들의 위치이다.

[0][0] [1][1] [2][2] [3][3]은 각 원소의 첫번째 부호임을 알 수 있다. 그리고 위로 올라갈수록 이전의 값들이 더해진 것에 대한 부호 변화를 알 수 있다.

3
+	1+(-3)+5+(-2)의 부호는 +
+	1+(-3)+5 의 부호는 +
-	1+(-3)의 부호는 -
+	1의 부호는 +

이 로직은 위 코드 함수 ck임을 알 수 있다.

 

def ck(idx):
    hap = 0
    for i in range(idx, -1, -1):
        hap += result[i]
        if hap == 0 and S[i][idx] != 0:
            return False
        elif hap < 0 and S[i][idx] >= 0:
            return False
        elif hap > 0 and S[i][idx] <= 0:
            return False
    return True

해당 값이 0인데 부호가 0이 아닐경우 False

해당 값이 0 미만인데 부호가 -1이 아닐경우 False

해당 값이  0보다 큰데 부호가 0보다 작거나 같은경우 False

위의 조건문 다 걸리지 않는다면 True

이러한 로직으로 부호판단을 한다.

 

 

 

def solve(idx):
    if idx == N:
        return True
    if S[idx][idx] == 0:
        result[idx] = 0
        return solve(idx+1)
    for i in range(1, 11):
        result[idx] = S[idx][idx] * i
        if ck(idx) and solve(idx+1):
            return True
    return False

여기서는 대각선의 부호는 해당 N의 부호의 성질을 이용한 부분이다.

만일 0이라면 해당 결과값 위치 또한 0이고 그 이외에는 재귀를 통해 ck함수와 그 뒤의 solve가 참일 경우 True을 호출하는 형식이다.