알고리즘/백준

맞춰봐 1248번 백준 파이썬

글을 쓰는 개발자 2020. 12. 8. 21:24
반응형

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

 

1248번: 맞춰봐

첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문

www.acmicpc.net

이 문제를 처음 접근했을 때 우선 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, 백트랙킹

https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 문제 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!"

hazung.tistory.com

  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임을 알 수 있다.

 

1
2
3
4
5
6
7
8
9
10
11
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
 cs

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

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

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

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

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

 

 

 

1
2
3
4
5
6
7
8
9
10
11
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
 cs

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

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

 

반응형