[백준] code.plus(브루트 포스 Part 1,JAVA)17088번, 등차수열 변환

문제 링크

17088번: 등차수열 변환

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. 수열에 숫자들은 +1, -1을 연산을 딱 한 번 사용 가능합니다.

2. 수열 A가 등차수열이 될 때 사용되는 최소 연산의 횟수를 결과로 출력합니다.

3. 연산을 사용해도 등차수열이 만들어지지 않으면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 연산을 사용하는 모든 경우를 탐색하여 등차수열이 되는지 확인합니다.

 

3. 모든 경우 탐색 후 최소 연산 사용 횟수를 결과로 출력합니다.

 

등차 수열 경우.

 

N == 1일 때

항상 등차수열이 성립하기 때문에 연산 횟수는 0이 최소값이 됩니다.

 

N > 1일 때

첫 A[0], A[1]의 차이가 균등하게 이어져가야 등차수열이 성립한다고 볼 수 있습니다.

 

첫 A[0], A[1]의 값에 연산을 사용한 경우와 안한 경우를 모두 탐색하면

 

(A[0], A[1]), (A[0], A[1]-1), (A[0], A[1]+1),

 

(A[0]-1, A[1]), (A[0]-1, A[1]-1), (A[0]-1, A[1]+1),

 

(A[0]+1, A[1]), (A[0]+1, A[1]-1), (A[0]+1, A[1]+1)

 

첫 시작인 9가지 경우에 모든 경우를 탐색합니다.

 

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N = 4

A = { 24, 21, 14, 10}

 

2. 연산을 사용하는 모든 경우를 탐색하여 등차수열이 되는지 확인합니다.

 

(A[0], A[1])으로 시작할 때

24 - 21 = -3

 

(A[1], A[2]) 비교하기

14 - 21 = -7 : X

15 - 21 = -6 : X

13 - 21 = -8 : X

 

등차 수열 진행 X

 

(A[0], A[1]-1)으로 시작할 때

24 - 20 = -4

 

(A[1]-1, A[2]) 비교하기

14 - 20 = -6 : X

15 - 20 = -5 : X

13 - 20 = -7 : X

 

등차 수열 진행 X

 

(A[0], A[1]+1)으로 시작할 때

24 - 22 = -2

 

(A[1]-1, A[2]) 비교하기

14 - 22 = -8 : X

15 - 22 = -7 : X

13 - 22 = -9 : X

 

등차 수열 진행 X

 

(A[0]-1, A[1])으로 시작할 때

23 - 21 = -2

 

(A[1], A[2]) 비교하기

14 - 21 = -7 : X

15 - 21 = -6 : X

13 - 21 = -8 : X

 

등차 수열 진행 X

 

(A[0]-1, A[1]-1)으로 시작할 때

23 - 20 = -3

 

(A[1]-1, A[2]) 비교하기

14 - 20 = -6 : X

15 - 20 = -5 : X

13 - 20 = -7 : X

 

등차 수열 진행 X

 

.....

(A[0]+1, A[1]-1)으로 시작할 때

25 - 20 = -5

 

(A[1]-1, A[2]) 비교하기

14 - 20 = -6 : X

15 - 20 = -5 : O

13 - 20 = -7 : X

 

(A[2]+1, A[3]) 비교하기

10 - 15 = -5 : O

11 - 15 = -4: X

9 - 15 = -6 : X

 

등차 수열 성립

연산 횟수 : 3번(A[0]+1, A[1]-1, A[2]+1, A[3])

 

3. 모든 경우 탐색 후 최소 연산 사용 횟수를 결과로 출력합니다.

 

최소 연산 사용 횟수 3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력값을 띄어쓰기 기준으로 나누었습니다.
• N==0일 때는 항상 등차수열 성립으로 결과 0을 BufferedWriter 저장하였습니다.
• N>1일 때 9가지 경우에 대한 search함수로 탐색하여 최소 연산 횟수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 입력된 기준으로 모든 경우를 탐색하여 등차수열이 성립되는지 확인합니다.
• search함수는 등차수열이 만들어질 때 연산 횟수의 최소값을 비교합니다.

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

public class Main {
    static int N, answer = Integer.MAX_VALUE;
    static int[] A;		//A 수열 정보 배열
    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());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        A = new int[N];
        //A수열에 대한 정보 저장
        for(int i=0;i<N;i++)
            A[i] = Integer.parseInt(st.nextToken());
        if(N==1)		//N==1일 때는 항상 등차수열 성립!
            bw.write("0");
        else{		//N>1일 때 처음 시작하는 9가지 경우로 모든 경우 탐색
            search(2, A[1] - A[0], 0, A[1]);
            search(2, A[1] - (A[0]-1), 1, A[1]);
            search(2, A[1] - (A[0]+1), 1, A[1]);

            search(2, (A[1]-1) - A[0], 1, A[1]-1);
            search(2, (A[1]-1) - (A[0]-1), 2, A[1]-1);
            search(2, (A[1]-1) - (A[0]+1), 2, A[1]-1);

            search(2, (A[1]+1) - A[0], 1, A[1]+1);
            search(2, (A[1]+1) - (A[0]-1), 2, A[1]+1);
            search(2, (A[1]+1) - (A[0]+1), 2, A[1]+1);

            if(answer == Integer.MAX_VALUE)		//등차 수열 성립하는 것이 없을 때
                bw.write("-1");	
            else		//등차 수열 성립시 최소 연산 횟수 BufferedWriter 저장
                bw.write(answer + "");
        }

        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //첫 시작하는 경우를 기준으로 등차 수열이 되는지 모든 경우를 탐색
    static void search(int depth, int dif, int count, int previousNum){
        if(depth == N){		//등차 수열 완성시
            answer = Math.min(answer, count);
            return;
        }
        //등차수열 되는지 탐색
        if(dif == A[depth] - previousNum)	//+0
            search(depth+1, dif, count, A[depth]);
        if(dif == (A[depth]-1) - previousNum)	//-1
            search(depth+1, dif, count+1, A[depth]-1);
        if(dif == (A[depth]+1) - previousNum)	//+1
            search(depth+1, dif, count+1, A[depth]+1);
    }
}