문제 : https://www.acmicpc.net/problem/1248
1248번: 맞춰봐
첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문
www.acmicpc.net
문제 요약 : 수를 조합하여 주어진 부호에 맞는 숫자 출력
| 입력 | 출력 |
| 1 ≤ N(숫자) ≤ 10 N(N+1)/2개의 부호 (+, -, 0) |
수를 조합하여 주어진 부호에 맞는 숫자 출력 |
JAVA
소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_1248.java
| 채점 번호 | 아이디 | 문제 번호 | 결과 | 메모리 | 시간 | 언어 | 코드 길이 |
| 31114112 | cbkpar | 1248 | 맞았습니다!! | 16852KB | 184ms | Java 11 | 1276B |
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int[][] op;
static int[] arr;
static int n;
static boolean chk;
static StringBuilder sb = new StringBuilder();
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int i,j,k;
n = Integer.parseInt(br.readLine());
op = new int[n][n];
arr = new int[n+1];
String str = br.readLine();
k = 0;
for(i=0;i<n;i++) {
for(j=i;j<n;j++) {
if(str.charAt(k)=='-') {
op[i][j] = -1;
}else if(str.charAt(k)=='0') {
op[i][j] = 0;
}else {
op[i][j] = 1;
}
k++;
}
}
chk = false;
btr(0);
System.out.println(sb);
}
static void btr(int k) {
if(chk) return;
if(k==n) {
for(int i=1;i<=n;i++) sb.append((arr[i]-arr[i-1])+" ");
chk = true;
return;
}
int mx = 10;
int mi = -10;
for(int i=0;i<=k;i++) {
if(op[i][k]==-1) {
mx = Math.min(mx, arr[i]-arr[k]-1);
}else if(op[i][k]==0) {
mx = Math.min(mx, arr[i]-arr[k]);
mi = Math.max(mi, arr[i]-arr[k]);
}else {
mi = Math.max(mi, arr[i]-arr[k]+1);
}
}
for(int i=mi;i<=mx;i++) {
arr[k+1] = arr[k] + i;
btr(k+1);
}
}
}숫자를 앞에서 부터 가능한 숫자를 구하여 가능한 모든 경우를 확인한다.
숫자의 범위가 -10 부터 10이므로 초기값을 최소 -10, 최대 10으로 설정 한 후
해당 순번의 부분합 부호를 확인하며 들어갈 수 있는 최소 또는 최대 값을 수정하며 탐색한다.
예제 )
4
-+0++++--+
'백준온라인' 카테고리의 다른 글
| [백준온라인] 9252번 LCS 2 (0) | 2021.07.31 |
|---|---|
| [백준온라인] 2467번 용액 (0) | 2021.07.30 |
| [백준온라인] 12018번 Yonsei TOTO (0) | 2021.07.28 |
| [백준온라인] 11441번 합 구하기 (0) | 2021.07.27 |
| [백준온라인] 12788번 제 2회 IUPC는 잘 개최될 수 있을까? (0) | 2021.07.26 |