[백준] code.plus(브루트포스-재귀,JAVA)1248번, 맞춰봐

문제 링크

1248번: 맞춰봐

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

 

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제에 핵심은

1. 수열의 가능한 숫자는 -10 ~ 10 입니다.

2. 각 숫자는 중복되어 사용 가능하다.

3. 부호는 [i][j]의 범위의 합의 조건이다.

 

처음 문제를 접했을 때 정확하게 이해되지는 않았습니다. (이해력 부족 ㅜ.ㅜ)

A4용지에 끄적이다 내용을 이해하게 되었습니다.

저는 부호에 관해서 이해가 잘 되지 않았는데 표로 표현하니 생각보다 간단한 문제였습니다.예제입력 1을 2차원 배열로 표현하면

인덱스(i/j)	0	1	2	3
0	-	+	0	+
1		+	+	+
2			-	-
3				+

[i][j]의 범위의 값의 합이

음수이면 '-'

양수이면 '+'

0이면 '0'

조건을 표현하는 것입니다.

i와 j는 수열의 몇 번째 숫자를 표현하는 것입니다.

 

배열

sign  : 입력되는 부호를 위에 표처럼 2차원 배열로 저장

 

result : 부호에 만족하는 수열의 값 저장

 

 

위에 sign, result와 재귀를 통해 부호에 만족하는 수열을 구하였습니다.

 

재귀를 통해 -10 ~ 10까지 수를 수열에 넣어보면서 부호에 조건에 맞는지 확인하였습니다.

 

부호에 조건이 맞는지 확인하는 방법은

 

1. 현재 수열의 값들을 모두 더합니다.

2. 현재 수열에서 길이 - 1 의 열을 기준으로 부호 조건에 만족하는지 확인합니다.

인덱스(i/j)	0	1	2	3
0	-	+	0	+
1		+	+	+
2			-	-
3				+

예를 들어 현재 수열의 길이가 3이면

3-1의 열의 부호가 현재 만족하는지 검사합니다.

행의 값이 커질 수록 합하는 범위는 줄어드는 것으로 모두 더한 값에서 해당 행의 대응하는 값을 빼줍니다.

 

예제입력 1로 살펴보면

현재 수열이 { -2,  5, -3}이 있다고 가정하면

1. 모든 수열의 값을 더한다.

-2 + 5 + (-3) = 0

2. 수열의 길이가 3으로 인덱스 2인 열의 부호를 확인합니다.

[0][2] = 수열 1~3번째 수의 합 = 0이고 부호도 '0'이기 때문에 조건에 만족

[1][2] = 수열 2~3번째 수의 합 = 모든 수열의 합에서 첫 번째 수열의 값을 뺀다 = 0 - (-2) = 2이다.

부호도 '+'이기 때문에 조건에 만족

[2][2] = 수열 3번째 수의 합 = [1][2] 합에서 2번째 수열의 값을 뺀다 = 2 - 5 = -3이다.

부호도 '-'이기 때문에 조건에 만족

 

위와 같은 방식으로 수열이 부호에 만족하는지 확인하도록 하였습니다.

 

문제에 해결알고리즘은

1. 부호를 2차원 배열 sign에 저장합니다.

2. 재귀를 통해 수열의 경우의 수를 구합니다.

3. 재귀 중 부호에 조건이 만족하는지 확인합니다.

4. 만족하는 수열이 만들어졌을 때 재귀를 종료하고 해당 수열을 출력합니다.

 

※ 처음에 저는 수의 중복을 허용하지 않는 수열을 만들도록 알고리즘을 작성하였지만 틀렸습니다.

문제를 다시 읽어보니 중복에 관한 내용이 없기 때문에 수열에 중복된 값이 들어가도 괜찮다고 판단하여 중복값 허용 수열을 만들어서 문제를 해결하였습니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• 수열을 만드는 guess와 수열이 부호에 조건에 만족하는지 확인하는 signCheck 함수를 만들었습니다.
• 부호에 만족하는 수열이 완성되었을 때 System.out.print()를 사용하여 결과를 출력하였습니다.
• 만족하는 수열을 출력하였기 때문에 System.exit(0)을 이용해 실행을 종료시켰습니다.

• guess는재귀와 부호의 조건 함수를 이용하여 만족하는 수열을 구하였습니다.
• signCheck는 위에 부호 조건을 확인하는 방법을 알고리즘으로 구현하여 확인하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int N;
	public static char[][] sign;	//부호 저장 2차원 배열
	public static int[] result;		//수열 값 저장 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        //------입력값 저장 및 배열 초기화--------
    	N = Integer.parseInt(br.readLine());
    	sign = new char[N][N];
    	result = new int[N];
    	String str = br.readLine();
    	int index = 0;
    	for(int i=0;i<N;i++) {
    		for(int j=i;j<N;j++) {
        		sign[i][j] = str.charAt(index++);
    		}
    	}
    	guess(0);		//함수 실행
    }
    public static void guess(int depth) {
    	if(depth==N) {
    		for(int i=0;i<N;i++) {
    			System.out.print(result[i] + " ");		//수열 출력
    		}
    		System.exit(0);		// 실행 종료
    	}
    	for(int i=-10;i<=10;i++) {
    		result[depth] = i;	//수열에 값 추가
    		if(signCheck(depth))	//부호 조건 확인
    			guess(depth+1);		//부호 조건 만족시 재귀 진행
    	}
    	return;
    }
    //------수열이 부호에 만족하는지 확인하는 함수-------
    public static boolean signCheck(int depth) {
    	int temp = 0;
    	for(int i=0;i<depth+1;i++) {
    		temp += result[i];		//현재 수열 값 모두 더하기
    	}
    	for(int i=0;i<depth+1;i++) {
    		if((temp>0 && sign[i][depth]!='+') 	//조건 만족 안할 시
    				|| (temp==0 && sign[i][depth]!='0') 
    				|| (temp<0 && sign[i][depth]!='-'))
    			return false;
    		temp -= result[i];	//다음 행은 범위가 좁아지기 때문에 빼기 진행
    	}
    	return true;
    }
}