골드의 길은 멀고도 험하다

#1248번 맞춰봐 https://www.acmicpc.net/problem/1248

1248번: 맞춰봐

이름부터가 재수없었던 문제이다.

 

내가 멍청해서인지 문제 이해부터 잘 되지 않았다.

 

위의 스토리는 그냥 시간끌기 및 혼동용이고

밑에 문단만 읽으면 된다.

 

4
-+0++++--+

다음과 같은 값이 들어올 경우 위 값을 matrix로 변환할 수 있다

 이 2차원 리스트의 의미는 다음과 같다.

첫 입력으로 받은 숫자만큼의 길이를 가진 수열을 구하는게 정답인데 (위의 경우는 4, _ _ _ _ ) 
[i][j]로 행렬에 접근할 경우, 정답 수열의 i번째 수 부터 j번째 수 까지의 합의 부호를 의미한다.

 

즉 matrix[1][0]의 의미는 수열의 1번 인덱스와 0번 인덱스의 값의 합의 부호를 의미한다. 즉 answer[0] + answer[1] > 0

 

따라서 i가 더 큰 경우의 행렬 좌표는 의미없는 좌표이다.

 

 

 

 

내가 놓쳤던 부분은 두가지이다.

1) 행렬로 변경하지 않고도 해결할 수 있을거라 생각했다 ->  존나빡셈

  : 문제에서 제안하는 방법은 꼭 활용하자

 

2) 행렬 접근시 i, j가 같은 경우를 캐치하지 못했다.

  :  matrix[0][0] 은 정답 수열의 첫번째 숫자의 부호 혹은 0을 의미했다.

 

처음 수열을 생성하려고 시도할 때 -10 ~ 10 까지의 숫자를 전부 대입했었다.

하지만 그럴 필요 없었다. 1~10까지의 수만 대입하고 거기에 matrix[0][0] (i == j 인 경우) 를 곱해주면 된다.

-> 문제를 푸는 key였다고 생각한다.

 

그 뒤에 재귀를 통한 검증절차를 밟으면 된다. 

 

검증함수 (check)를 구현하는 방법은 어렵지 않았다.

 

1번 인덱스에 위치한 값을 검증하기 위해서는

matrix 상에서 j를 1로 고정해 놓은 뒤에

1보다 작은 값 방향으로 0번 index까지 i를 루프를 돌며

martrix[i][j]를 호출한다. 

이런 방향으로 값을 호출하는 것이다. 

호출이 될 때는, 검증하고자 하는 index의 값과 그 전 인덱스들의 값을 더해서 matrix에서 가져온 부호와 같은지 검증한다. 다를 경우에는 False를 return하면 된다.

 

matrix상에서 해당되는 모든 값을 검증했는데도 오류가 하나도 없다면 그 때 True를 return 한다.

 

 

 

 

 

 

N = int(input())
signs = [x for x in input()]
# 이 시그널들을 matrix화 시켜야 편하다.
# 이 부분을 간과한터라 시간이 오래걸린듯.
S = [[0]*N for _ in range(N)]

for i in range(N):
    for j in range(i, N):
        tmp = signs.pop(0)

        if tmp == "+":
            S[i][j] = 1
        elif tmp == "-":
            S[i][j] = -1
        else:
            S[i][j] = 0


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


def solve(idx):
    if idx == N:
        return True

    for i in range(1, 11):
        # matrix 에서 idx,idx에 위치한 값이 본인의 부호이기 때문이다!!
        result[idx] = S[idx][idx]*i
        # 따라서 -10~+10까지 루프를 돌릴 필요가 없다. 0이면 0나오고. 개꿀
        if check(idx) and solve(idx+1):
            return True


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

조금 인상적인 부분은 solve함수의 if부분인데, check와 재귀의 종료조건을 동시에 사용하는게 인상적이었다.

많이 참고하면서 코드를 작성했는데, 배운바가 많다.