[백준, Java] 27210번, 신을 모시는 사당(누적합, DP)

문제 링크

27210번: 신을 모시는 사당

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. N개의 돌상이 존재하며 각 돌상은 왼쪽 또는 오른쪽을 바라보고 있습니다.

2. 금색으로 칠해진 돌상을 기준으로 깨달음의 양을 구할 수 있습니다.

3. 금색으로 칠하는 행동은 연속한 몇 개의 돌상을 1번 진행합니다.

4. 금색을 1번 칠했을 때 얻을 수 있는 최대 깨달음의 양을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 돌상의 순서에 맞게 누적합을 진행합니다.

 

3. 누적합을 진행하면서 얻은 최대값을 결과로 출력합니다.

 

 

누적합(깨달음 계산)

 

현재 방향에 대한 깨달음의 양이 1씩 증가하면서 누적합을 진행합니다.

 

= 반대 방향의 석상에 대한 깨달음의 양은 1이 줄어들어야 합니다.

 

 

★ 반대 방향의 석상에 대한 깨달음의 양이 0인 경우, 1을 줄이지 않고 다음 반대 방향 석상이 연속되는 시작 위치가 됩니다.

 

 

위 경우를 왼쪽, 오른쪽 석상을 구분하여 누적합을 진행합니다.

 

DP(현재까지 금색을 칠한 최상의 경우)

 

누적합으로 석상이 개수를 적립한다면, 이전까지 왼쪽, 오른쪽에 대한 최상의 경우에서 깨달음의 정보를 저장합니다.

 

0 : 왼쪽(1)

 

1 : 오른쪽(2)

 

DP[2][0] : 2번째 석상까지 왼쪽을 바라보는 석상의 최대 깨달음 양

 

DP[3][1] : 3번째 석상까지 오른쪽을 바라보는 석상의 최대 깨달음 양

 

 

 

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

 

예제입력 1.

 

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

 

N : 5

 

석상

1	2	3	4	5
1	1	2	1	2

 

 

2. 돌상의 순서에 맞게 누적합을 진행합니다.

 

누적합 및 DP을 통해 깨달음의 양을 계산!

 

1번째 석상일 때

 

DP	0	1(1)	2(1)	3(2)	4(1)	5(2)
왼쪽	0	1
오른쪽	0	0

왼쪽 방향 깨달음의 양이 1만큼 증가하였습니다.

 

= 오른쪽 방향의 깨달음의 양이 0이기 때문에, 다음 오른쪽 석상이 나올 때를 기준으로 오른쪽 석상은 금색 칠하기를 시작합니다.

 

2번째 석상일 때

 

DP	0	1(1)	2(1)	3(2)	4(1)	5(2)
왼쪽	0	1	2
오른쪽	0	0	0

왼쪽 방향 깨달음의 양이 1만큼 증가하였습니다.

 

= 오른쪽 방향의 깨달음의 양이 0이기 때문에, 다음 오른쪽 석상이 나올 때를 기준으로 오른쪽 석상은 금색 칠하기를 시작합니다.

 

3번째 석상일 때

 

DP	0	1(1)	2(1)	3(2)	4(1)	5(2)
왼쪽	0	1	2	1
오른쪽	0	0	0	1

 

오른쪽 방향 깨달음의 양이 1만큼 증가하였습니다.

 

= 왼쪽 방향의 깨달음의 양이 0이 아니기 때문에 깨달음의 양이 감소됩니다.

 

4번째 석상일 때

 

DP	0	1(1)	2(1)	3(2)	4(1)	5(2)
왼쪽	0	1	2	1	2
오른쪽	0	0	0	1	0

 

왼쪽 방향 깨달음의 양이 1만큼 증가하였습니다.

 

= 오른쪽 방향의 깨달음의 양이 0이기 때문에, 다음 오른쪽 석상이 나올 때를 기준으로 오른쪽 석상은 금색 칠하기를 시작합니다.

 

5번째 석상일 때

 

DP	0	1(1)	2(1)	3(2)	4(1)	5(2)
왼쪽	0	1	2	1	2	1
오른쪽	0	0	0	1	0	1

 

오른쪽 방향 깨달음의 양이 1만큼 증가하였습니다.

 

= 왼쪽 방향의 깨달음의 양이 0이 아니기 때문에 깨달음의 양이 감소됩니다.

 

 

탐색 종료.

 

3. 탐색한 최단 거리를 결과로 출력합니다.

 

 

 

DP	0	1(1)	2(1)	3(2)	4(1)	5(2)
왼쪽	0	1	2	1	2	1
오른쪽	0	0	0	1	0	1

최대값 : 2

 

2을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여  석상의 정보를 띄어쓰기 기준 나누었습니다.
• 석상 순서에 맞게 누적합으로 깨달음의 양을 쌓고, DP로 최상의 경우일 때에 깨달음의 양을 저장합니다.
• 탐색을 하면서 계산한 최대 깨달음의 양을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

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

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 N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[][] DP = new int[N+1][2];
        int result = 0;
        //입력되는 석상을 기준으로 누적합 및 DP계산
        for(int i=1;i<=N;i++){
            int num = Integer.parseInt(st.nextToken());
            int reverse = num-- % 2;	//반대 석상 index
            //현재 방향의 석상 최대의 깨달음의 양 
            DP[i][num] = DP[i-1][num] + 1;
            //반대 방향을 기준으로 칠한 최대 경우가 1개 이상일 때
            if(DP[i-1][reverse] > 0){
                DP[i][reverse] = DP[i-1][reverse] - 1;
            }
            //최대값인지 비교하기
            result = Math.max(result, DP[i][num]);
        }
        //결과 BufferedWriter 저장
        bw.write(String.valueOf(result));		//결과 출력
        bw.flush();
        bw.close();
        br.close();
    }
}