[백준, Java] 1239번, 차트 (브루트포스)

문제 링크

1239번: 차트

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 차트는 원형 차트를 띄고 있습니다.

2. 원의 중심을 지나는 선은 원을 이등분하는 선입니다.

3. 원의 중심을 지나는 선의 최대 개수를 결과로 출력합니다.

4. 조사한 개의 수의 합은 항상 100입니다.

 

알고리즘 진행 순서.

 

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

 

2. 모든 경우를 탐색해서 원의 중심을 지나는 선의 최대 개수를 구합니다.

 

3. 탐색을 통해 구한 최대 개수를 결과로 출력합니다.

 

 

원의 중심이 지나는 선

 

원의 중심을 지난다 = 원을 이등분 하는 선?

 

 

즉, 원의 중심을 지나는 직선의 개수를 구해라!!!

 

 

차트의 3가지 경우.

 

가장 큰 값이 50%보다 클 때

원의 중심을 지나는 선(직선)을 만들 수 없습니다!!

 

가장 큰 값이 50%보다 클 때

 

원의 중심을 지나는 선(직선)은 항상 1개만 만들 수 있습니다!!

 

가장 큰 값이 50%보다 작을 때

차트를 구성하는 모든 경우를 비교해서 직선의 최대 개수를 구해야 한다.

 

직선이 되는 조건

12시와 6시를 기준으로 같은 양만큼 범위를 차지하면 직선을 만들 수 있습니다.

Ex.

12시 기준 : 10%

6시 기준 : 10%

 

즉, 2개의 직선이 만들어집니다.

 

※ 차트의 시작은 항상 12시로 시작하기 때문에 차트를 채우다가 6시부터 시작하면 직선이 성립됩니다.

→ 위 그림에 12시에서 6시로 이어지는 직선이 만들어지는 경우를 말하고 있습니다.

 

예제입력 1.

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

N : 4

10 40 10 40

 

2. 모든 경우를 탐색해서 원의 중심을 지나는 선의 최대 개수를 구합니다.

 

차트의 최대값(40)은 50%보다 작다.

 

→ 차트를 구성하는 모든 경우를 비교해서 직선의 최대 개수를 구해야 한다. 

 

모든 경우 탐색

 

 

원의 중심을 지나는 선(직선) : 2개

원의 중심을 지나는 선(직선) : 2개

 

원의 중심을 지나는 선(직선) : 2개

 

.....

 

 

3. 탐색을 통해 구한 최대 개수를 결과로 출력합니다.

 

 

 

최대 개수 : 2개

 

2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 개의 수를 저장합니다.
• 최대 퍼센트를 기준으로 차트의 3가지 경우에 따라 진행합니다.
• 최대값이 50%미만일 때 search 함수를 이용하여 차트 영역을 배분하는 모든 경우의 탐색을 진행합니다.
• 탐색이 끝난 뒤 원의 중심을 지나는 선의 최대 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 재귀를 통해 차트 영역을 배분하는 모든 경우를 탐색합니다.
• search함수는 비트마스킹을 이용해 영역을 배분 유무를 확인합니다.

 

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int[] chart;	//차트 정보 저장 배열
    static boolean[] check;	//차트 직선 지나는 범위 배열
    //fullMask : 비트마스킹을 통한 모든 차트 내용 사용 확인 값
    static int result = 0, N, fullMask;
    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));
        N = Integer.parseInt(br.readLine());
        int max  = -1;	//차트 내 최대값 변수
        chart = new int[N];
        check = new boolean[51];
        fullMask = (1 << N) - 1;	//fullMask 초기화
        StringTokenizer st= new StringTokenizer(br.readLine()," ");
        //차트 값 저장
        for(int i=0;i<N;i++){
            chart[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, chart[i]);	//최대값 비교
        }
        if(max > 50)	//50% 이상 존재 시, 직선 X
            bw.write("0");
        else if(max == 0)	//50% 존재 시, 직선 1개
            bw.write("1");
        else{		// 50% 미만일 때, 모든 경우 탐색
            check[0] = true;	//12시 시작값 기준 시작
            search(0, 0,false, 0);	//모든 경우 탐색
            bw.write(String.valueOf(result));	//최대 개수 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //차트 모든 경우 탐색하는 재귀함수
    static void search(int cnt, int sum, boolean flag, int mask){
        if(mask == fullMask){	//차트 완성시.
            result = Math.max(result, cnt);
            return;
        }
        //다음 차트에 들어갈 영역 탐색
        for(int i=0;i<N;i++){
            if((mask & (1<<i)) >= 1)	//이미 탐색한 영역일 때
                continue;
            int temp = chart[i] + sum;

            if(!flag){	//12시부터 시작했을 때 영역
                if(temp>= 50){	//50퍼를 넘어서 6시 이후 구역으로 넘어갈 때
                    if(check[temp % 50]) {	//직선이 생길 때
                        search(cnt+1, temp % 50, true, mask | (1 << i));
                    }else	//직선이 생기지 않을 때
                        search(cnt, temp%50, true, mask|(1<<i));
                }else{	//50퍼를 넘어가지 않을 때
                    check[temp] = true;	//해당 영역 선 생성
                    search(cnt, temp, false, mask | (1<<i) );	//다음 영역 탐색
                    check[temp] = false;	//해당 영역 선 제거
                }
            }else{	//6시부터 시작했을 때 영역
                if(check[temp]) {	//직선이 생길 때
                    search(cnt + 1, temp, true, mask | (1 << i));
                }else	//직선이 생기지 않을 때
                    search(cnt, temp, true, mask | (1<<i));
            }
        }
    }
}