백준 27219번: 신을 모시는 사당 (Java 코드)

 

풀이

solved.ac 기준 골드 5 난이도의 문제이다. dp 알고리즘을 이용해 문제를 해결할 수 있다.

 

 dp[] 배열을 만들고 i번째 돌상을 색칠할 경우에 얻을 수 있는 최대의 깨달음 양을 dp[i]에 저장해야 한다. 이 때 돌상이 바라보는 방향은 1(왼쪽)과 2(오른쪽) 두 가지 종류가 있으므로 dp배열도 두 개를 생성한다.(왼쪽으로 바라보는 불상으로 깨달음을 얻을 수도, 오른쪽으로 바라보는 불상으로 깨달음을 얻을 수도 있으므로!)

 

dp 관련 코드는 다음과 같다.

if (dir[i] == 1) {
    dp1[i] = (dp1[i-1] + 1 > 1) ? dp1[i-1] + 1 : 1;
    dp2[i] = dp2[i-1] - 1;
}
else {
    dp1[i] = dp1[i-1] - 1;
    dp2[i] = (dp2[i-1] + 1 > 1) ? dp2[i-1] + 1 : 1;
}

 

이전 불상에 이어서 연속으로 i번째 불상을 색칠할 때 얻을 수 있는 깨달음 양은 dp[i-1] + 1이다.

반대로 i번째 불상을 첫 번째로 색칠했을 때 얻을 수 있는 깨달음 양은 1이다.

둘 중 최대값을 dp[i]에 저장한다.

 

1번 방향을 바라보고 있을 때에는 dp1[]에, 2번 방향을 바라보고 있을 때에는 dp2[]에 저장해야 한다.

그리고 반대 방향의 dp[] 배열에는 이전 최대값인 dp[i-1]에 1을 빼고 저장한다.

 

 

결과 코드

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

class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
		
        int n;
        n = sc.nextInt();

        int dir[] = new int[n];
        int dp1[] = new int[n];
        int dp2[] = new int[n];
        int dp1Max = 1, dp2Max = 1;
		
        for (int i = 0; i < n; i++) {
            dir[i] = sc.nextInt();
        }
        
        if (dir[0] == 1) {
        	dp1[0] = 1;
        	dp2[0] = 0;
        }
        else {
        	dp1[0] = 0;
        	dp2[0] = 1;
        }
        
        for (int i = 1; i < n; i++) {
        	if (dir[i] == 1) {
        		dp1[i] = (dp1[i-1] + 1 > 1) ? dp1[i-1] + 1 : 1;
        		dp2[i] = dp2[i-1] - 1;
        		
        		if (dp1[i] > dp1Max) dp1Max = dp1[i];
        	}
        	else {
        		dp1[i] = dp1[i-1] - 1;
        		dp2[i] = (dp2[i-1] + 1 > 1) ? dp2[i-1] + 1 : 1;
        		
        		if (dp2[i] > dp2Max) dp2Max = dp2[i];
        	}
        }
        
        if (dp1Max > dp2Max) System.out.println(dp1Max);
        else System.out.println(dp2Max);
	}
}