👀 문제
https://www.acmicpc.net/problem/1248
👊 도전
1. 설계
- n개의 숫자를 -10~10까지 모두 확인하며 문자열의 조건을 만족하는지 확인한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
static int n;
static char[][] array;
static int[] result;
public static void dfs(int cnt) {
if(cnt==n) {
for(int i=0;i<n;i++)
System.out.print(result[i]+" ");
System.exit(0);
return;
}
for(int i=-10;i<=10;i++) {
result[cnt]=i;
if(check(cnt)) dfs(cnt+1);
}
}
public static boolean check(int idx) {
for(int i=0;i<=idx;i++) {
int sum=0;
for(int j=i;j<=idx;j++) {
sum+=result[j];
if(array[i][j]!=(sum==0?'0':(sum>0?'+':'-')))
return false;
}
}
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
String str=scan.next();
array=new char[n][n];
int idx=0;
for(int i=0;i<n;i++) {
for(int j=i;j<n;j++) {
array[i][j]=str.charAt(idx);
idx++;
}
}
result=new int[n];
dfs(0);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 문자열을 이차원배열에 저장한다
- 문제의 요지는 위 조건을 만족하는 숫자 n개를 리턴하는 것이다.
- 예를 들어, (0,0)은 첫 번째 숫자가 -2, 음수이므로 -가 된다.
- (0,1)은 -2+5=3이므로 양수, +이다.
- (0,2)는 -2+5-3=0이므로 0이다.
- 이와 같이 이전 항들의 누적합과 현재 숫자를 더했을 때의 부호가 주어진 배열 값과 같아야한다.
- 따라서 문자열을 이차원배열에 적절히 저장하여 이를 이용한다.
- DFS를 이용한다
- 숫자 범위는 -10~10이므로 모두 대입해 조건을 확인한다. 도중에 맞지 않다면 버린다.
- 따라서 DFS를 이용해 조건에 대한 모든 경우를 탐색하는 방식으로 진행한다.
- dfs()에서 for문을 통해 임의의 숫자 i를 배정하고, check()를 통해 현재까지의 숫자가 조건에 맞는지 확인한다.
👏 해결 완료!
참고
- 맞춰봐 [백준 1248][JAVA][골드 3][백트래킹][DFS] https://toastfactory.tistory.com/206