BAEKJOON : 1248

No. 1248

1. Problem

2. My Solution

• [-10, -9, ... 0 ....9, 10] 에서 길이 N인 수열을 구하면서 하나씩 판단 (중복 순열)
• PyPy3 5400ms, Python3 시간초과

import sys

def solution(level):
    if level >= n:
        if check(arr,level) == True:
            print(*arr)
            exit()
    else:
        for i in range(21):
            arr[level] = nums[i]
            if check(arr,level+1) == False:
                continue
            solution(level+1)
    

def check(arr,n):
    for i in range(n):
        temp = 0
        for j in range(i,n):
            temp += arr[j]
            if check2(temp,i,j) == False:
                return False
    return True


def check2(sum, i,j):
    if sum > 0 and s[i][j] =='+':
        return True
    elif sum == 0 and s[i][j] == '0':
        return True
    elif sum < 0 and s[i][j] =='-':
        return True
    else:
        return False

n = int(sys.stdin.readline())
matrix = sys.stdin.readline().rstrip()
s = [[0]*n for _ in range(n)]

cnt = 0             
for i in range(n):
    for j in range(i,n):    # (n) 하면 s[1][0] 이 될 수도있음 
        s[i][j] = matrix[cnt]
        cnt += 1            # 두 번째 입력으로 들어온 부호배열을 앞에서부터 하나씩 삽입 

nums = [i for i in range(-10,11,1)]
arr = [0] * n

solution(0)

3. Others' Solutions

• -10 ~ 10 까지의 수에서 순열을 구하는 것은 시간이 오래걸림, 좀 더 효율적인 백트래킹 기법이 필요함
• 문제의 입력으로 나와있는 것을 행렬화하여 표현하면 아래처럼됨. 이 때 결과로 출력되는 각 숫자들의 부호는 출력되는 순서(인덱스)에 맞게 [0][0], [1][1], [2][2],[3][3] 위치에 있는 부호와 일치함
• 이를 이용하여 순열을 구성할 때 -10 ~ 10 사이에서 구하지 않고 음수부분, 0, 양수부분 으로 백트래킹

import sys

def check(n):
    temp = 0
    for i in range(n,-1,-1):
        temp += arr[i]
        if temp > 0 and s[i][n] =='+':
            continue
        elif temp == 0 and s[i][n] == '0':
            continue
        elif temp < 0 and s[i][n] =='-':
            continue
        else:
            return False
    return True


def solution(level):
    if level >= n:
        print(*arr)
        exit()
    else:
        if s[level][level] == '0':        # 결과의 level 번째 요소 자리가 0이면
            arr[level] = 0
            if check(level) == True:
                solution(level+1)
        elif s[level][level] == '+':      # 결과의 level 번째 요소 자리가 양수이면
            for i in range(1,11):
                arr[level] = i
                if check(level) == True:
                    solution(level+1)
        else:                             # 결과의 level 번째 요소 자리가 음수이면
            for i in range(-10,0):
                arr[level] = i
                if check(level) == True:
                    solution(level+1)
           

n = int(sys.stdin.readline())
matrix = list(sys.stdin.readline().rstrip())
s = [[0]*n for _ in range(n)]

k = 0
for i in range(n):
    for j in range(i,n):            # (n) 하면 s[1][0] 이 될 수도있음 
        s[i][j] = matrix[k]         # 두 번째 입력으로 들어온 부호배열을 앞에서부터 하나씩 삽입 
        k += 1

arr = [0] * n
solution(0)

4. Learned

• 문제에 주어진 단서를 좀 더 활용하여 백트래킹할 수 있는 부분을 생각해내자
• 궁금한 건 못 참지