디저트

면접 대비

시간 제한1초메모리 제한1024 MB

요약

1부터 N까지 번호가 붙은 소 사이에 +, -, . 중 하나를 넣어 식의 값이 0이 되는 경우를 찾고, 처음 20개와 전체 개수를 출력합니다.

난이도: 보통10점 중 4점
유형: 백트래킹, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

FJ는 저녁 식사를 기다리며 줄을 서는 소들에게 새 규칙을 정했다. 소 N마리(3 ≤ N ≤ 15)는 순서대로 줄을 서야 하고, 이웃한 소 사이마다 "+", "-", "." 중 하나가 적힌 냅킨을 놓아야 한다. 디저트를 받으려면 소의 번호와 냅킨으로 만든 수식의 값이 0이 되어야 한다. "." 냅킨 덕분에 소들은 더 큰 수를 만들 수 있다. 소 7마리의 예를 보자.

1 - 2 . 3 - 4 . 5 + 6 . 7

이는 1-23-45+67을 뜻하며, 값은 0이다. 여러분이 할 일은 소들이 디저트를 먹도록 돕는 것이다. (참고: "... 10 . 11 ..."은 계산에서 1011이라는 수를 사용한다.)

입력

정수 N이 한 줄에 주어진다.

출력

가능한 수식 중 처음 20개를 한 줄에 하나씩 출력한 뒤, 가능한 답의 총 개수를 정수 한 줄로 출력한다. 각 수식 줄은 수, 냅킨, 수, 냅킨 순서의 형식을 따른다. 출력은 사전순이며, "+"가 "-"보다 앞에, "-"가 "."보다 앞에 온다. 만들 수 있는 수식이 20개보다 적으면 모든 수식을 출력한다.

예제1

예제 1

입력

예상 출력

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