[문제풀이] 사칙연산

업데이트:

문제 링크 : 사칙연산

풀이 시간 : 60분

1. 문제 풀이

DP를 활용한 문제

음수를 빼면 양수 더하기로 되는 것을 잘 생각해서 최대 값을 유지하는 문제

3차원 배열을 통해 각 단계별 최대값(0)과 최소값(1)을 저장

최종적으로 최대값 리턴

2. 소스 코드

    public int solution(String arr[]) {
		// map에 저장, 0은 최대값을 저장, 1은 최소값을 저장
		int[][][] map = new int[arr.length / 2 + 1][arr.length / 2 + 1][2];
		boolean[] op = new boolean[arr.length / 2];
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				map[i][j][0] = Integer.MIN_VALUE;
				map[i][j][1] = Integer.MAX_VALUE;
			}
		}
		// 입력값 저장
		for (int i = 0; i < op.length; i++) {
			map[0][i][0] = Integer.parseInt(arr[i * 2]);
			map[0][i][1] = Integer.parseInt(arr[i * 2]);
			if (arr[i * 2 + 1].charAt(0) == '+') {
				op[i] = true;
			}
		}

		map[0][op.length][0] = Integer.parseInt(arr[arr.length - 1]);
		map[0][op.length][1] = Integer.parseInt(arr[arr.length - 1]);
		for (int i = 1; i < map.length; i++) {
			for (int j = 0; j < map.length - i; j++) {
				for (int k = 0; k < i; k++) {
					if (op[i + j - k - 1]) {
						// 더하기 일때는 최대값끼리 더해서 가장 큰 최대값 만들기
						map[i][j][0] = Math.max(map[i][j][0], map[i - 1 - k][j][0] + map[k][i + j - k][0]);
						// 최소값끼리 더해서 가장 작은 최소값 만들기
						map[i][j][1] = Math.min(map[i][j][1], map[i - 1 - k][j][1] + map[k][i + j - k][1]);
					} else {
						// 빼기는 최대 값에서 최소값을 빼서 가장 큰 값 만들기
						map[i][j][0] = Math.max(map[i][j][0], map[i - 1 - k][j][0] - map[k][i + j - k][1]);
						// 최소값에서 최대값을 빼서 가장 작은 값 만들기
						map[i][j][1] = Math.min(map[i][j][1], map[i - 1 - k][j][1] - map[k][i + j - k][0]);
					}
				}
			}
		}
		return map[arr.length / 2][0][0];
	}

3. 후기

Matrix chain multiplication을 응용해서 풀었다.

다만 저 아이디어가 생각나는 것이 오래 걸렸고 단순히 최대값만 저장해서 풀었서 틀렸다.

음수를 빼기 연산을 하면 양수가 되어서 최소값도 저장해서 구해줘야 했다.

“1-1-1+1-1+1” 연산의 최대 값이 4가 나와야 한다.

1-((1-(1+1))-(1+1))의 순서가 최대가 된다.

참고