[백준] 1248번(python 파이썬) 맞춰봐

문제 이름도 얄미운데 이해하기 힘들었다. 이 문제 지어낸 사람의 세계관이란...

암튼 핵심을 말하자면 1차원 배열을 2차원 형태로 바꿔줘야하며 숫자와 비교하기 위해 str을 int형태로 바꿔줘야한다.

부등호를 int형태로 바꾸려면 '+' = 1, '-' = -1, '0' = 0 로 바꿔주면 된다.

시간초과때문에 pypy3로 바꿔서 제출해야한다.

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


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

N = int(input())
temp = list(input())
S = [[0] * N for _ in range(N)]
cnt = 0
result = [0] * N
for i in range(N):
    for j in range(i, N):
            if temp[cnt] == '-':
                S[i][j] = -1
            elif temp[cnt] == '0':
                S[i][j] = 0
            else:
                S[i][j] = 1
            cnt += 1
            
solve(0)
print(' '.join(map(str, result)))

나중에 기억안날때 보기 위헤 푸는 과정을 아래와 같이 그려보았다. 

728x90