소 저녁 식사 주기

  • N(1~15)마리의 소들을 순서대로 세워놓고 각 소들 사이에 +, -, .의 셋 중 한가지가 쓰여진 냅킨을 배치해서 최종 결과가 0이 되도록 하는 문제
  • .은 숫자를 연결하는 부호가 됨 (예: 10.11 => 1011)
  • 소의 수 N이 입력되었을 때 처음 20줄에 대해 가능한 20가지 답을 출력하는데 사전 순으로 앞선 것을 출력한다
  • +가 가장 앞서고 -, . 순서이다

N = 7
1 + 2 - 3 + 4 - 5 - 6 + 7
1 + 2 + 3 + 4 - 5 + 6 - 7
1 - 2 + 3 + 4 - 5 + 6 - 7
1 - 2 - 3 - 4 - 5 + 6 + 7
1 - 2 . 3 + 4 + 5 + 6 + 7
1 - 2 . 3 - 4 . 5 + 6 . 7
6 가지

  • 수와 수 사이에 사용할 수 있는 연산자는 모두 3종류
  • 수와 수 사이의 개수는 N-1개이므로 가능한 경우의 수는 3의 N-1승 가지 이다
  • N의 최대값이 15이므로 3의 14승 = 4,782,969 가지가 최대치가 됨
  • 두 수 사이에 +나 -를 사용하는 경우에는 dfs(step, a)로 해결
  • 하지만 .을 고려한다면 dfs(step, a, b)로 구현해야 함
  • 여기서 a는 직전에 등장한 + 또는 - 이전까지의 결과이고 b는 직전에 등장한 + 또는 - 이후부터 0개 이상의 .을 계산하여 하나의 수로 만든 결과
  • 새로운 +나 -가 나오면 a에 b에 더하는 연산만 한다 (-일 때엔 b를 음수로 변환)
  • 마지막 단계에서 a + b === 0 인지를 확인
  • N의 최대값이 15이므로 만들 수 있는 가장 큰 수는 123456789101112131415이지만 결과값이 0이어야 하므로 12345678910 이상의 수는 고려하지 않아도 된다 (나머지인 1112131415가 12345678910보다 작기 때문)