[Programmers] 사칙연산

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/1843

코딩테스트 연습 - 사칙연산

분할 정복과 DP 알고리즘을 조합한 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. A 구간과 B 구간 사이의 연산자가 +라면 A 구간 내 연산 결과 중 최댓값과 B 구간 내 연산 결과 중 최댓값을 더해야 최댓값을 구할 수 있습니다.

1.1 A 구간과 B 구간 사이의 연산자가 -라면 A 구간 내 연산 결과 중 최대값과 B 구간 내 연산 결과 중 최솟값을 더해야 최댓값을 구할 수 있습니다.

2. 따라서, dp를 이용해 구간 내 연산 결과 최대, 최소값을 구해줍니다.

3. 2번에서 구한 결과를 토대로 구간 내 최대값을 반환해줍니다.

 

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~