[SWEA] 8338. 계산기

문제

다은이는 방탈출 카페에서 마지막 문제를 풀고있다.

마지막 문제는 다음과 같다

N개의 수 a1,a2, ⋯, aN이 있다. 이수들은 차례대로 계산기에 입력 해야만 하는데,

수를 입력하는 중간 중간에 연산자를 반드시 하나 입력을해야만 한다.

연산자에는 더하기 혹은 곱하기만 입력할 수 있다.

정확히 말해서, a1, (+ or x),a2, (+ or x), ⋯, (+ or x), aN를 계산기에 입력하는 것이다.

수식을 계산할 때 연산자의 우선 순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다.

계산기에 계산된 결과로 나올 수 있는 값 중 최대값을 구하여 방 탈출에 성공하자.

 

풀이방법

동적 계획법(DP, Dynamic Programming) 알고리즘으로 간단히 풀 수 있는 문제이다.

 

n * 2 크기의 2차원 배열을 만든다. 각 행에는 이전까지의 연산의 최대값에 덧셈을 한 결과와 곱셈을 한 결과가 저장된다.

 

즉,

 

i행 0열에는 a[1]에서 a[i-1]까지 덧셈이나 곱셈연산을 했을 때의 최대값 + ai

 

i행 1열에는 a[1]에서 a[i-1]까지 덧셈이나 곱셈연산을 했을 때의 최대값 * ai

 

점화식을 세우면 아래와 같다.

 

dp[i][0] = max(dp[i-1][0], dp[i-1][1]) * ai 

 

dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + ai

 

소스코드

package samsung;

import java.util.*;

public class s_8338 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int n = sc.nextInt();
			int[][] a = new int[n][2];
			
			for(int i = 0; i < n; i++) {
				int tmp = sc.nextInt();
				if(i == 0) {
					a[i][0] = tmp;
					a[i][1] = tmp;
				}
				else {
					a[i][0] = Math.max(a[i-1][0], a[i-1][1]) * tmp;
					a[i][1] = Math.max(a[i-1][0], a[i-1][1]) + tmp;
				}
			}
			System.out.println("#" + t + " " + Math.max(a[n-1][0], a[n-1][1]));
		}
	}
}