백준: 1248 맞춰봐

문제

1248번: 맞춰봐

 

문제 풀이

 -10 ~ 10를 선택하면, 선택된 숫자를 기반으로 한 S 배열의 정보를 입력으로 받는다. 해당 배열 정보를 입력받으면, 그를 바탕으로 순열 들과 비교하여 만족하는 순열을 찾으면 된다. 문제의 예제 입력의 S는 -+0++++--+로 이는 다음과 같이 나타낼 수 있다.

 

  첫 행의 정보(i == 0)는 다음과 같은 경우의 수를 나타낸다.

• j == 0
  • (0, 0) < 0
• j == 1
  • (0, 0) + (0, 1) > 0
• j == 2
  • (0, 0) + (0, 1) + (0, 2) == 0
• j == 3
  • (0, 0) + (0, 1) + (0, 2) + (0, 3) > 0

  두 번째 행의 정보는 i == 1 부터 각 자리 숫자의 합이 + + + 을 만족하는 수를 의미한다. 따라서 만족하는 순열을 입력값을 통해 반환하면 된다. 또한 여러 개의 답을 찾을 경우 아무거나 반환하면 되므로, 하나라도 찾게 된다면 반환하고 종료하면 된다.

 

코드

def available(idx):
    sum_num = 0
    for i in range(idx, -1, -1):
        sum_num += check[i]
        if s[i][idx] == '+' and sum_num <= 0:
            return False
        if s[i][idx] == '-' and sum_num >= 0:
            return False
        if s[i][idx] == '0' and sum_num != 0:
            return False
    return True


def dfs(depth):
    if depth == n:
        print(*check)
        exit(0)
    for i in range(-10, 11):
        check[depth] = i
        if available(depth):
            dfs(depth + 1)
        check[depth] = -11


if __name__ == "__main__":
    n = int(input())
    s = [[0] * n for _ in range(n)]
    input_s = list(input())
    check, k = [-11] * n, 0
    for i in range(n):
        for j in range(i, n):
            s[i][j] = input_s[k]
            k += 1
    dfs(0)

 Python3로 제출하면 시간초과가 발생하여 PyPy3로 제출하여 통과하였다. 다른 언어는 해당 로직으로 통과하는 것을 보아.. 파이썬이 느리다는 자기 합리화를 했다...😂