[백준, Java] 17307번, 색깔 통일하기, (누적합)

문제 링크

17307번: 색깔 통일하기

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 버튼은 누르면 양옆에 인접한 버튼끼리 연결되어 있다.

2. 색깔은 0 ~ (C-1)개가 존재하며, 버튼을 누르면 (X + 1) % C 의 값으로 변경됩니다.

3. 색깔이 변경되었을 때, 옆에 같은 색의 연속한 버튼도 같이 변경됩니다.

4. 버튼은 1개만 계속 누를 수 있습니다.

5. 최소 횟수가 같으면 더 작은 버튼을 결과로 출력합니다.

6. 모든 색을 동일하게 만드는 버튼의 번호와 최소 횟수를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

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

 

2. 누적합을 통해서 각 버튼을 누를 때 색을 통일하는 횟수를 구합니다.

 

3. 횟수 중 최소 개수와 버튼의 번호를 결과로 출력합니다.

 

 

누적합(좌우 방향으로 버튼의 색을 통일하는 횟수)

 

1번 버튼부터 N번까지 동일한 색을 만드는 누적합

 

▶ 현재 버튼에 대해서 오른쪽에 존재하는 버튼들을 동일한 색으로 맞추는 횟수

 

N번 버튼부터 1번까지 동일한 색을 만드는 누적합

 

▶ 현재 버튼에 대해서 왼쪽에 존재하는 버튼들을 동일한 색으로 맞추는 횟수

 

위 상황이 만족하는 이유는, 동일한 버튼이 되면 해당 버튼이 누를 때마다 같이 색이 변화하기 때문입니다.

 

예를 들어,

 

C = 4일 때

버튼	1	2	3	4
색	1	2	3	1
누적합	0	1	2	4

1번 버튼을 기준으로 오른쪽 동일한 색을 맞출 때

 

1

2

3

1

 

2

2

3

1

 

3

3

3

1

 

0

0

0

1

 

1

1

1

1

 

2번 버튼을 기준으로 오른쪽 맞출 때

 

★ 2번 버튼 전까지는 신경쓰지 않아도 되기 때문에

 

4번(4) - 2번(1) = 3번

 

점화식으로 표현하면

 

Sum[] :  누적합

 

f(x) = Sum[N] - Sum[x]

 

왼쪽도 동일하게 적용되므로 점화식으로 표현하면

 

f(x) = Sum[1] - Sum[x]

 

각 버튼의 최소 횟수를 만드려면

 

해당 버튼을 기준으로 왼쪽 방향, 오른쪽 방향으로 동일한 색을 만들 때 큰 값이 됩니다.

 

Why??

 

적은 방향에 대해서 모두 같은 색으로 바꾸었어도, 큰 방향이 동일한 색으로 만들어야 하기 때문입니다.

 

요약하면, 큰 방향을 같은 색으로 맞추면 자동적으로 작은쪽은 동일한 색이 되어있습니다.

 

※예제 입력 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 1.

 

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

 

N : 5

 

C : 4

 

버튼	1	2	3	4	5
색	1	0	0	3	1

 

2. 누적합을 통해서 각 버튼을 누를 때 색을 통일하는 횟수를 구합니다.

 

누적합 구하기

 

버튼	1	2	3	4	5
색	1	0	0	3	1
누적합(→)	0	3	3	6	8
누적합(←)	4	3	3	2	0

 

점화식을 이용해서 각 버튼의 동일한 색을 만드는 최소 횟수 구하기

 

1번

 

Math.max(rightSum[5] - rightSum[1], leftSum[1] - leftSum[1]) = Math.max(8, 0) = 8

 

2번

 

Math.max( rightSum [5] - rightSum [2], leftSum [1] - leftSum [2]) = Math.max(5, 1) = 5

 

3번

 

Math.max( rightSum [5] - rightSum [3], leftSum [1] - leftSum [3]) = Math.max(5, 1) = 5

 

4번

 

Math.max( rightSum [5] - rightSum [4], leftSum [1] - leftSum [4]) = Math.max(2, 2) = 2

 

5번

 

Math.max( rightSum [5] - rightSum [5], leftSum [1] - leftSum [5]) = Math.max(0, 4) = 4

 

 

버튼	1	2	3	4	5
버튼 최소 횟수	8	5	5	2	4

 

 

 

 

 

3. 횟수 중 최소 개수와 버튼의 번호를 결과로 출력합니다.

 

 

버튼	1	2	3	4	5
버튼 최소 횟수	8	5	5	2	4

 

 

 

4

2

을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 버튼의 색깔의 정보를 띄어쓰기 기준 나누었습니다.
• calButtonPush을 이용해서 왼쪽, 오른쪽 방향 색을 동일하게 만드는 누적합을 구합니다.
• 누적합을 통해서 각 버튼이 동일한 버튼으로 만드는 최소 횟수를 구합니다.
• 각 버튼 중에서 최소 횟수를 결과로 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• calButtonPush는 다음 버튼의 색으로 변경하는데 필요한 버튼 누르는 횟수를 구합니다.

결과코드

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 {
    //Button의 초기 색 저장하는 배열
    static int[] button;
    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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken()) - 1;
        st = new StringTokenizer(br.readLine()," ");
        button = new int[N+1];
        //입력값 저장
        for(int i=1;i<=N;i++){
            button[i] = Integer.parseInt(st.nextToken());
        }
        //왼쪽, 오른쪽 방향 누적합 구하기
        long[][] sum = new long[N+1][2];	
        //sum[][0] :  오른쪽, sum[][1]:왼쪽
        for(int i=2;i<=N;i++){
            sum[i][0] = sum[i-1][0] + calButtonPush(i, true, C);
            sum[N-i+1][1] = sum[N-i+2][1] + calButtonPush(N-i+1, false, C);
        }
        long result = Long.MAX_VALUE;
        int index = 0;
        //각 버튼 최소 횟수 구하기
        for(int i=1;i<=N;i++){
            long temp = Math.max(sum[N][0] - sum[i][0], sum[1][1] - sum[i][1]);
            //최소값 구하기
            if(result > temp){
                result = temp;
                index = i;
            }
        }
        //결과값 BufferedWriter 저장
        bw.write(String.valueOf(index));
        bw.newLine();
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();

    }
    //다음 색으로 변할 때 버튼을 누르는 횟수 계산하는 함수
    static int calButtonPush(int index, boolean flag, int C){
        //으론쪽
        if(flag){
            if(button[index-1] <= button[index]){	//더 큰 값으로 색을 변경할 때
                return button[index] - button[index-1];
            }else{		//더 작은 값으로 색을 변경할 때
                return (C - button[index-1]) + button[index] + 1;
            }
        }else{	//왼쪽
            if(button[index+1] <= button[index]){	//더 큰 값으로 색을 변경할 때
                return button[index] - button[index+1];
            }else{		// 더 작은 값으로 색을 변경할 때
                return (C - button[index+1]) + button[index] + 1;
            }
        }
    }
}