글 읽기 - dp로 풀었는데 반례를 모르겠습니다.

dks301 4년 전 0

간단하게 설명드리면 a[i]는 입력을 char배열로 저장(짝수는 숫자, 홀수는 연산자), i번째 자릿수에 있는 수가 i-2(바로 앞의 수)번째 수와 괄호로 묶이면 d[i][0]에 안묶이면 d[i][1]에 최댓값을 저장하는 방식으로 구현했습니다.(d에서 최댓값을 저장할때 짝수 idx만 사용)

점화식은

1. d[i][0]

1-1. i번째 수가 i-2번째 수와 묶인다면 괄호가 겹치면 안되므로, i-2번째 수와 i-4번째 수는 괄호로 묶이지 않아야한다.

1-2. a[i-2], a[i]를 괄호로 묶어 a[i-1]로 연산 후에 d[i-4][0]과 d[i-4][1] 중 큰것과 a[i-3]로 연산하면 최댓값이다.

2. d[i][1]

2-1. i번째 수가 i-2번째 수와 묶이지 않는다면, i-2번째 수는 i-4번째 수와 묶여도 되고 묶이지 않아도 된다.

2-2. max(d[i-2][0], d[i-2][1])과 a[i]를 a[i-1]로 연산하면 최댓값이다.

N이 1일때나, 제가 만들어본 반례는 모두 통과하는데 제출하자마자 바로 틀립니다.

로직상에서 틀린부분이나 반례 좀 부탁드립니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		char[] a = br.readLine().toCharArray(); // 짝수자리 숫자, 홀수자리 연산자
		
		int[][]d = new int[N][2]; // i번째 자리에 있는 수가 i-2자리에 있는 수와 괄호로 묶일때 j=0, 안묶일때 j=1
		d[0][0] = d[0][1] = Character.getNumericValue(a[0]);
		if (N >= 3) { // N이 1일때, 잘못 된 index참조 방지
			d[2][0] = d[2][1] = operation(Character.getNumericValue(a[0]), a[1], Character.getNumericValue(a[2]));

			for (int i = 4; i < N; i += 2) { 
				int temp = operation(Character.getNumericValue(a[i - 2]), a[i - 1], Character.getNumericValue(a[i])); // a[i-2]와 a[i]를 a[i-1]연산자로 계산
				d[i][0] = operation(Math.max(d[i - 4][0], d[i - 4][1]), a[i - 3], temp); // i-4번쨰까지 최댓값과 위 연산값을 a[i-3]연산자로 계산
				d[i][1] = Math.max(operation(d[i - 2][0], a[i - 1], Character.getNumericValue(a[i])), operation(d[i - 2][1], a[i - 1], Character.getNumericValue(a[i])));
				// i-2 자리까지 최댓값과 a[i]의 값을  a[i-1]연산자로 계산
			}
		}

		System.out.println(Math.max(d[N - 1][0], d[N - 1][1])); // 최댓값 출력
	}

	public static int operation(int val1, char op, int val2) {
		switch (op) {
		case '+':
			return val1 + val2;

		case '-':
			return val1 - val2;

		case '*':
			return val1 * val2;
		}

		return Integer.MIN_VALUE; // error!
	}
}

dks301 4년 전 0

19
2*1-1*1+2*2-9*8-9*9

앞에가 최소가 되어서 음수를 곱하는게 최대가 될수 있는 반례가 있었습니다.

gtkim4617 4년 전 0

그래서 저 반례의 답이 뭔가요?

chansb 1년 전 0

input)

19
2*1-1*1+2*2-9*8-9*9

output)

189

댓글을 작성하려면 로그인해야 합니다.