[BaekJoon] 1248 맞춰봐

🔦 문제 링크

✍️ 풀이

---

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

  • 먼저 입력받은 부호를 쓰기 쉽게 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 

📝 정리

---

🎈 참조

---

참고블로그