BOJ(맞춰봐)(1248)

작성일 | In

맞춰봐 1248

  • -10부터 10까지 N개의 정수(중복 없음)로 이루어진 수열 A가 있다. (N<=10)
  • S[i][j] = A[i]+A[i+1] =…A[j]가 0보다 크면 +, 작으면 -, 같으면 0이 들어가 있는 2차원 배열
  • s라는 배열이 있을 때, 수는 -10~10까지만 사용 가능
  • 수열의 크기의 제한은 10이다.

  • 이 때 가능한 a를 찾는 문제

  • 수의 갯수 -10~10까지 21개 있음
  • 21개의 자연수를 적절히 10개의 자리에 넣어서 ,s를 만드는 것이다.
  • 엄청 오랜 시간이 걸린다.
  • 21개의 수를 10개의 자리에 넣는다. 21^10은 엄청 큰 수.
  • 경우의 수가 많다.

일단 함수를 작성해보자

bool go (int index){
    if (index == n){
        return ok();
    }
    for (int i = -10; i<=10; i++){
        ans [index] = i;
        if (go (index+1)) return true;
    }
    return false;
}
  • 문제는 시간이 너무 오래 걸린다.
  • 함수호출을 자를 수 있는 조건을 커팅 조건이라고 해보자.
  • 커팅 조건은 무엇이 있을까? -> 바로 대각선 줄이다.
  • 대각선 줄이 의미하는 건, i라는 수의 부호를 의미.

  • A[i][i]는 i 번째 수의 부호가 있을 수 밖에 없다.

  • 양수인 경우에는 1~10
  • 음수인 경우 -10~1

  • 0인 경우에는 0을 넣어서 계산을 할 수 있다.

  • idx번째 수를 결정하면, 0~idx수는 변하지 않는다.
  • 따라서, 모든 sign[k]index를 go(index)에서 검사할 수 있다.
def check(index):
    s = 0
    for i in range(index,-1,-1):
        s += ans[i]
        if sign[i][index] == 0:
            if s != 0:
                return False
        elif sign[i][index] < 0:
            if s >= 0:
                return False
        elif sign[i][index] > 0:
            if s <= 0:
                return False
    return True

def go(index):
    if index == n:
        return True
    if sign[index][index] == 0:
        ans[index] = 0
        return check(index) and go(index+1)

    for i in range(1, 11):
        ans[index] = i * sign[index][index]
        if check(index) and go(index+1):
            return True
    return False

n = int(input())
s = input()
sign = [[0]*n for _ in range(n)]
ans = [0]*n
cnt = 0
for i in range(n):
    for j in range(i,n):
        if s[cnt] == '0':
            sign[i][j] = 0
        elif s[cnt] == '+':
            sign[i][j] = 1
        else:
            sign[i][j] = -1
        cnt += 1

go(0)
print(' '.join(map(str,ans)))

-

참고자료 codeplus

0%