알고리즘 풀이 - 백준 1248(맞춰봐, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

-10 ~ 10까지의 정수만 아는 데, 최초 숫자 N이 주어지면 그 구간 내 N개의 숫자를 무작위로 고르게 된다.

이 때, 각 전체 숫자 간 구간합 (N * (N+1) / 2)개를 모두 구할 때, 각각의 결과를 +, 0, -로 구분 할 수 있다. 그 결과 값이 2번째 줄에 주어질 때, 가능성이 있는 숫자 N개를 출력하는 문제

 

 

2. 풀이

 

이 문제는 다 읽었는데 초반 윗부분은 대부분 불 필요한 내용이어서 초반 이해하려고 할 때 헷갈렸다. 이 문제는 예를 들면 다음과 같다.

N = 2이고 결과 값이 +++라고 한다면 후보가 되는 N개의 숫자는 1, 2일 수 있는 것이다.

 

왜냐하면 +++라는 것은 모든 구간 합이 양수라는 의미인데, 각 구간합이 다음과 같기 때문이다.

1=1(양수)
1+2=3 (양수)
2=2(양수)

즉, 앞에서부터 진행되는 모든 각 숫자 간의 합을 구하여 전체 결과가 주어진 결과값과 일치하기만 하면 된다.

 

N개의 숫자가 있으면 N x (N+1) / 2개의 부호가 생성된다. 그것을 행렬로 저장한다면 아래와 같이 된다.

예를 들어 N=4일 때, N개의 숫자가 -1 1 3 2라면 아래와 같은 행렬이 만들어지게 된다.

 

위와 같이, 각 index의 숫자에서 시작하는 모든 구간합의 결과에 따른 부호를 저장하게 된다.

 

여기서 알 수 있는 점이 하나 있다. column, row가 같은 것, 예를 들어 (0, 0), (1, 1), (2, 2), (3, 3)의 부호가 0이라면 자체 숫자로 0이어야만 한다.

+, -의 부호인 경우에는 다른 숫자가 될 수 있지만 자기 자신만으로 0을 만들려면 0인 경우만 있기 때문이다. 나머지 경우에는 현재 부호에 따라 1 또는 -1을 곱해가면서 적합한 숫자를 집어 넣고 해당 결과가 유효한지 체크한다.

 

이 문제는 가능한 숫자 조합을 모두 파악하여 결과를 도출해야 하므로 완전 탐색(재귀)를 이용해서 풀 수 있다.

하지만 단순히 모든 숫자 조합을 체크하게 되면 0을 제외하더라도 최대 $20^{10}$번을 체크해야 한다. 도저히 짧은 시간에 해결할 수 없다. 따라서 중복되는 검사를 수행하지 않도록 코드를 작성해야 한다.

 

또한 재귀 함수의 return 문을 boolean으로 작성하였다. 왜냐하면 전체 N개의 숫자가 모두 선택된 경우가 아니라 각 숫자를 대입할 때마다 검사를 수행해야 하기 때문이다.

중복되는 검사를 수행하지 않도록 하기 위함이므로 이와 같이 작성한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;

public class Main{
    static int n;
    static String line;
    static int[][] mark;       // 부호 정보 저장하는 배열
    static int[][] calc;       // 부호에 따라 결정된 숫자들에 의해 계산된 값을 저장하는 배열
    static int[] num;          // 선택된 숫자들을 저장하는 배열
    static boolean complete;   // n개 숫자 모두 선택되었는지 확인하는 변수
    static BufferedWriter bw;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 주어진 숫자, 부호를 모두 읽음
        n = Integer.parseInt(br.readLine());
        line = br.readLine();
        
        // 부호 정보를 배열로 2차원으로 저장
        // +는 1, 0은 0, -는 -1로 저장함
        mark = new int[n][n];
        
        int k = 0;
        
        // 배열에 부호가 -이면 -1, +이면 1, 0이면 0으로 저장
        for(int i=0; i < n; i++){
            for(int j=i; j < n; j++){
                char c = line.charAt(k++);
                mark[i][j] = c == '-' ? -1 : c == '+' ? 1 : 0;
            }
        }
        
        // 선택된 숫자 저장하는 배열 초기화
        num = new int[n];
        
        solve(0);
        
        for(int ans : num){
            bw.write(String.valueOf(ans) + " ");
        }
        bw.flush();
        br.close();
    }
    
    private static boolean solve(int idx){
        // n개의 숫자가 모두 선택되었다면 성공적인 것이므로 더 이상 재귀가 돌지 않도록 설정
        if(idx == n) {
            return true;
        }
        
        // (0, 0)등이 0이라면 무조건 0으로 해야 함
        if(mark[idx][idx] == 0){
            num[idx] = 0;
            return solve(idx+1);
        }
        
        // 1~10까지의 숫자를 테스트하되, 부호가 -면 -1을 곱해서 진행함
        for(int i=1; i < 11; i++){
            num[idx] = mark[idx][idx]*i;
            if(check(idx) && solve(idx+1)) return true;
        }
        return false;
    }
    
    // 숫자가 정해졌다면 idx 부분 이전까지는 이미 유효한 결과를 냈다는 것이다.
    // 따라서 idx 부분부터 시작하면 현재 체크하고자 하는 숫자가 반드시 포함된다.
    // 즉, 이전 숫자들 간의 구간 합은 따지지 않고 이번 숫자가 반드시 포함된 경우만 체크하여
    // 전체 check 횟수를 현저히 낮출 수 있다.
    private static boolean check(int idx){
        int sum = 0;
        for(int i=idx; i >= 0; i--){
            sum += num[i];
            if(mark[i][idx] == 0){
                if(sum != 0) return false;
            } else if(mark[i][idx] > 0){
                if(sum <= 0) return false;
            } else {
                if(sum >= 0) return false;
            }
        }
        return true;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.