[BaekJoon] 1248 맞춰봐

pyh8618·2020년 9월 25일
0
post-thumbnail

🔦 문제 링크

✍️ 풀이


  • 백트래킹으로 푸는 문제이다.

    • 먼저 입력받은 부호를 쓰기 쉽게 S의 행 단위로 나눈다.
    1. -10 ~ 10의 숫자 중 하나를 선택한다.
    2. V에 추가한 모든 값의 합이 현재 인덱스의 부호와 일치하면 V에 선택한 값 추가
    3. 부호 조건과 다르다면 추가하지 않고 다음 수를 선택한다.
    4. 이 과정을 반복하다가 인덱스가 부호 갯수와 일치하면 그 때의 V 원소들을 출력한다.

🛠 코드


n = int(input())
a = [[0]*n for _ in range(n)]
b = list(input())
v, k = [], 0

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


def solve(idx):
    if idx == n:
        print(''.join(map(str, v)))
        exit(0)
    for i in range(-10,11):
        v.append(i)
        if possible(idx):
            solve(idx+1)
        v.pop()

for i in range(n):
    for j in range(i, n):
        a[i][j] = b[k]
        k += 1
solve(0)

✍️ 다른 풀이


  • 먼저 부호- , +로 변환 후 저장해 둔다

  • 값을 정할 때 인덱스의 부호를 해당 값에 곱해줘서 부호를 정한다.

  • 이를 통해 범위를 1 ~ 10 까지로 줄일 수 있다.

  • 0 의 경우 예외 처리를 해줘야 한다.

🛠 다른 코드


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

📝 정리


🎈 참조


참고블로그

profile
Go Go

0개의 댓글