문제
1부터 N까지의 정수를 순서대로 나열하고, 인접한 두 수 사이에 +, -, 혹은 공백( )을 삽입하여 식을 만든다. 공백으로 연결된 숫자들은 하나의 수를 이루며 (예: 1 2 3 → 123), 이 식의 값이 0이 되는 모든 경우를 사전순으로 출력한다.
입력
첫째 줄에 테스트 케이스 수 T, 이후 T줄에 N이 주어진다. (1 ≤ N ≤ 9)
출력
각 테스트 케이스마다 값이 0이 되는 식을 사전순으로 출력하고, 테스트 케이스 사이에 빈 줄을 출력한다.
예제
입력
2
3
7출력
1+2-3
1-2+3-4+5-6+7
1-2-3+4+5-6+7
...풀이
핵심 아이디어: DFS(백트래킹)로 각 자리 사이에 공백/+/-를 선택하는 모든 경우를 탐색한다. 공백은 현재 누적 중인 숫자에 다음 자릿수를 이어 붙이는 연산이다.
- 상태 정의:
dfs(d, n, sum, op, str)d: 현재 깊이 (1부터 N까지)n: 현재 누적 중인 숫자 (아직sum에 반영되지 않은 값)sum: 지금까지 확정된 합산 결과op:n에 적용할 부호 (+1 또는 -1)str: 현재까지 구성된 식 문자열
- 기저 조건:
d == N이면sum + n * op를 계산해 0이면 결과에 추가한다. - 공백:
n * 10 + (d+1)로 숫자를 이어 붙이고 부호는 유지한다. +:sum + n * op를 새 합으로,n = d+1,op = +1로 새 숫자를 시작한다.-: 동일하게op = -1로 새 숫자를 시작한다.- 사전순 보장: 공백,
+,-순으로 재귀하면 자연스럽게 사전순이 된다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day346BOJ7490영만들기 {
static int N, T;
static StringBuilder ans;
static StringBuilder sb;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
N = Integer.parseInt(br.readLine());
ans = new StringBuilder();
dfs(1, 1, 0, 1, "1");
// sb.append(ans);
System.out.println(ans);
}
// System.out.println(sb);
br.close();
}
private static void dfs(int d, int n, int sum, int op, String str) {
if (d == N) {
sum += (n * op);
if (sum == 0)
ans.append(str + "\n");
return;
}
dfs(d + 1, n * 10 + (d + 1), sum, op, str + " " + Integer.toString(d + 1));
dfs(d + 1, d + 1, sum + (n * op), 1, str + "+" + Integer.toString(d + 1));
dfs(d + 1, d + 1, sum + (n * op), -1, str + "-" + Integer.toString(d + 1));
}
}복잡도
- 시간: O(3^N) — N이 최대 9이므로 최대 3^8 = 6561가지 경우
- 공간: O(N) — 재귀 스택 깊이 N