0 만들기_백준7490_백트래킹

-문제-

 

-문제 접근-

1부터 N까지의 숫자 사이에 세 가지 기호(공백, '+', '-')를 삽입하여 생성된 수식의 결과가 0이 되는 모든 경우를 찾아야 하는 문제입니다.

 

1. 백트래킹

• 백트래킹(재귀) 기법을 사용하여 1부터 N까지 숫자 사이의 (N-1)개 위치마다 가능한 3가지 기호(공백, '+', '-')를 모두 삽입하는 경우의 수를 생성합니다.
• 재귀 호출을 통해 한 단계씩 숫자를 추가하면서 완성된 수식을 만들고, 최종 숫자(N)에 도달하면 해당 수식을 평가합니다.

2. evaluate 함수

• 생성된 수식은 공백, '+' 및 '-'를 포함합니다.
• 공백 처리: 공백은 인접한 숫자를 연결하여 하나의 수로 만들어야 합니다. ("1 2"는 12)
• 연산 처리: '+'와 '-'를 만날 때마다, 지금까지 이어진 숫자를 정수로 변환하고, 앞서 저장한 부호를 곱하여 총합에 누적합니다.
• 마지막 숫자도 처리하여 최종 계산 결과를 얻고, 이 결과가 0이면 수식을 결과에 포함합니다.

 

-코드-

 

-코드 설명-

evaluate 

 

• 문자열 순회:
  • 각 문자를 하나씩 검사하면서 숫자(0~9)는 temp에 추가합니다.
  • 공백은 무시하여, temp에 숫자를 이어 붙이도록 합니다.
• 연산자 만날 때:
  • '+' 또는 '-'를 만나면, 지금까지 모은 숫자(temp)를 정수로 변환해 이전 부호(sign)를 곱한 후 sum에 누적합니다.
  • temp를 초기화하고, 현재 연산자에 따라 sign 값을 갱신합니다.
• 마지막 숫자 처리:
  • 반복문이 끝난 후에도 남은 temp에 대해 같은 과정을 진행합니다.
• 최종 결과 반환:
  • 계산된 sum을 반환하여 수식의 결과값을 도출합니다.

 

backtrack

 

• 기저 사례(Base Case):
  • 현재 숫자(cur)가 N에 도달하면, 수식이 완성된 것입니다.
  • evaluate 함수를 호출하여 수식의 결과가 0이면 results 벡터에 저장합니다.
• 재귀 호출 (Recursive Step):
  • 아직 N에 도달하지 않은 경우, 다음 숫자(cur + 1)를 문자열로 변환해 next에 저장합니다.
  • 현재 수식에 대해 세 가지 경우를 고려합니다.
    • 공백(" "):
      현재 숫자와 다음 숫자를 이어 붙여 하나의 수로 처리합니다.
    • '+' 삽입:
      현재 수식에 '+'와 다음 숫자를 추가합니다.
    • '-' 삽입:
      현재 수식에 '-'와 다음 숫자를 추가합니다.
  • 각각의 경우에 대해 backtrack을 재귀 호출하여, 숫자들을 차례로 추가합니다.

main

 

• 테스트 케이스 처리:
  • 먼저 테스트 케이스 수 T를 입력받고, 각 케이스마다 N 값을 입력받습니다.
  • results.clear()로 이전 케이스의 결과를 지우고,
    backtrack("1", 1, N)을 호출하여 "1"부터 시작해 완성된 수식을 생성합니다.
• 정렬 및 출력:
  • 생성된 수식을 ASCII 순으로 정렬합니다.
  • 각 수식을 한 줄씩 출력하고, 테스트 케이스 사이에는 빈 줄을 출력하여 구분합니다.

 

 

-END-