[백준, Java] 21818번, Do You Know Your ABCs?, (완전 탐색)

문제 링크

21818번: Do You Know Your ABCs?

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. (A, B, C)을 기반으로 N개의 값을 만들어야 합니다.

2. N개의 값은 A, B, C, A+B, A+C, B+C, A+B+C으로 안에 만족해야 합니다.

3. (A, B, C)조합으로 N개의 값을 만족하는 경우의 개수를 결과로 출력합니다.

4. (1 ≤ A ≤ B ≤ C)을 만족해야 합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. A,B,C가 나올 수 있는 값들을 찾은 뒤, 조합을 통해서 N개가 만족하는 경우의 개수를 탐색합니다.

 

3. 탐색을 통해 얻은 경우의 개수를 결과로 출력합니다.

 

A, B, C 나올 수 있는 값 찾기

 

N개의 값에서 나올 수 있는 값 : A, B, C, A + B, A + C, B + C, A + B + C

 

최소 N개의 값이 4개이기 때문에 A, B, C 모두 N개의 값에 영향을 끼치고 있습니다.

 

 

예를 들어, N이 4일 때 A을 최대한 사용하지 않으면

 

B, C, B+C : 3개

 

A, A+B, A+C, A+B+C : 4개 중 1개가 사용되게 됩니다.

 

 

즉, (A, B, C)에 대해서는 항상 사용되게 됩니다.

 

A을 사용하는 경우 : A, A+B, A+C, A+B+C

 

A을 구할 때  : A - 0 , (A + B) - B, (A+C) - C, (A+B+C) - (B+C)으로 볼 수 있습니다.

 

즉, N개의 값 안에서의 차이가 A가 될 수 있는 값들이 됩니다.

 

B, C도 동일하게 A처럼 적용을 한다면

 

B을 구할 때  : B - 0 , (B + A) - A, (B+C) - C, (A+B+C) - (A+C)

 

C을 구할 때  : C - 0 , (C + A) - A, (C+B) - B, (A+B+C) - (A+B)

 

 

즉, N개의 값의 차이가 (A, B, C)가 될 수 있는 값입니다.

 

※ A - 0, B - 0, C - 0을 진행해주기 위해서는 N개의 값에 존재하지 않는 0을 추가해주어야 합니다.

 

조합을 통해 N개가 만족하는지 탐색

 

(A, B, C)가 될 수 있는 값을 구하였다면??

 

조합을 통해서 (A, B, C)에 대한 모든 조합을 만들어봅니다.

 

조합을 만들 때에는 1가지 조건을 만족해야 합니다.

 

조건 : 1 ≤ A ≤ B ≤ C

 

조건을 만족한다면, 해당 조합에 대해서 N개의 값들이 A, B, C, A+B, A+C, B+C, A+B+C으로 만들어 질 수 있는지 확인합니다.

 

→ 모든 N개의 값이 만들어진다면, 해당 조합은 문제의 조건에 만족하는 경우의 수가 되는 것입니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

※테스트 케이스 2번을 진행하겠습니다.

 

N : 4

 

[N개의 값]

 

4

5

7

8

 

 

2. A,B,C가 나올 수 있는 값들을 찾은 뒤, 조합을 통해서 N개가 만족하는 경우의 개수를 탐색합니다.

 

 

[A, B, C가 나올 수 있는 수]

 

 

N개의 값 + 0 : { 0, 4, 5, 7, 8 }

 

나올 수 있는 값 : 1, 2, 3, 4, 5, 7, 8

 

 

[조합 진행]

 

A :  1, B : 1,  C : 1

 

→ 나올 수 있는 값이 { 1, 2, 3 }으로써 N개의 모든 값을 포함하고 있지 않아서 조건에 맞는 조합이 아닙니다.

 

A :  1, B : 1,  C : 2

 

→ 나올 수 있는 값이 { 1, 2, 3, 4 }으로써 N개의 모든 값을 포함하고 있지 않아서 조건에 맞는 조합이 아닙니다.

 

....

 

 

A :  1, B : 3,  C : 4

 

→ 나올 수 있는 값이 { 1, 3, 4, 5, 7, 8 }으로써 N개의 모든 값을 포함하고 있어서 조건에 맞는 조합입니다.

 

 

A :  1, B : 4,  C : 7

 

→ 나올 수 있는 값이 { 1, 4, 5, 7, 8, 11, 12 }으로써 N개의 모든 값을 포함하고 있어서 조건에 맞는 조합입니다.

 

 

A :  3, B : 4,  C : 5

 

→ 나올 수 있는 값이 { 3, 4, 5, 7, 8, 9, 12 }으로써 N개의 모든 값을 포함하고 있어서 조건에 맞는 조합입니다.

 

...

 

 

3. 탐색을 통해 얻은 경우의 개수를 결과로 출력합니다.

 

[조건에 만족하는 조합]

 

A :  1, B : 3,  C : 4

 

A :  1, B : 4,  C : 7

 

A :  3, B : 4,  C : 5

 

3 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 N개의 값을 띄어쓰기 기준 나누었습니다.
• (A, B, C)에 대해 조건을 만족하는 경우의 개수를 탐색하는 search함수를 진행합니다.
• 탐색을 통해 얻은 경우의 개수를 Bufferedwriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 N개의 값 + 0을 기반으로 차이를 통해 A, B, C가 될 수 있는 값을 탐색합니다.
• search함수는 A, B, C가 될 수 있는 값을 기반으로 조합을 통해 조건에 만족하는 경우의 수를 탐색합니다.
• check함수는 (A, B, C)조합으로 N개의 값을 만들 수 있는지 확인합니다.

결과코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //각 테스트 케이스 진행
        for(int tc = 0; tc < T; tc++){
            int N = Integer.parseInt(br.readLine());
            //inputs[0] = 0으로써, 이미 0을 추가한 것입니다.
            int[] inputs = new int[N+1];
            st = new StringTokenizer(br.readLine()," ");
            //입력되는 N개의 값 저장
            for(int i=1;i<=N;i++){
                inputs[i] = Integer.parseInt(st.nextToken());
            }
            //조건에 맞는 조합의 개수 탐색 진행
            int result = search(inputs, N);
            //조건에 맞는 경우의 수 BufferedWriter 저장
            bw.write(String.valueOf(result));
            bw.newLine();
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //A,B,C가 될 수 있는 값 탐색 후, 조합을 통해 경우의 수 구하는 함수
    static int search(int[] inputs, int n){
        Set<Integer> values = new HashSet<>();
        //A, B, C가 될 수 있는 값 탐색
        for(int i=0;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                //N개의 값 + 0에 대해서 차이값 구하기.
                int dif = Math.abs(inputs[j] - inputs[i]);
                if(dif > 0){
                    values.add(dif);
                }
            }
        }
        int cnt = 0;
        //(A, B, C) 조합을 통한 조건 만족하는 경우의 수 구하기.
        for(int A : values){
            for(int B : values){
                for(int C : values){
                    //1 ≤ A ≤ B ≤ C 만족하는지 확인
                    if(A > B || B > C){
                        continue;
                    }
                    //N개의 값이 모두 존재하는지 확인
                    if(check(A, B, C, inputs, n)){
                        cnt++;
                    }
                }
            }
        }
        //경우의 수 반환
        return cnt;
    }
    //N개의 수가 (A, B, C)으로 만들 수 있는지 확인하는 함수
    static boolean check(int A, int B, int C, int[] inputs, int n){
        int AB = A + B;
        int BC = B + C;
        int AC = A + C;
        int ABC = A + B + C;
        //N개의 값 비교하기.
        for(int i=1;i<=n;i++){
            //N개의 값 중 1개라도 만들 수 없는 경우
            if(inputs[i] != AB && inputs[i] != BC && inputs[i] != AC && inputs[i] != ABC
                    && inputs[i] != A && inputs[i] != B && inputs[i] != C){
                return false;
            }
        }
        return true;
    }
}