99클럽 코테 스터디 20일차 TIL - 1843 사칙연산

1843. 사칙연산 / c++ / level4 / 1시간+

문제 및 코드

접근 방식

동적 계획법

1. 식을 적절히 괄호로 감싸서 계산 순서를 정했을 때 나올 수 있는 최대 값을 구하는 문제였다.
2. dp라는건 결국 이전 값을 다음 계산에 활용할 수 있다는 것이므로, 이걸 어떻게 문제에 대입할 수 있을지 생각해봤다.
3. 연산자 하나에 대해 양쪽 옆에 새로운 부분식이 생긴다고 했을 때, 다시 그 작은 식을 재귀적으로 해결할 수 있을거라고 생각했다.
4. 그 부분식의 계산값을 저장해두면, 매번 계산하지 않아도 되므로, 이 방법으로 풀었더니 통과했다. (이 때, 포인트는 부분식의 최대값과 최소값을 동시에 저장해서, 연산자가 - 일 때 오른쪽 부분식의 최대값과 최소값 중 어떤걸 활용하는지를 정하는 것이었다.)

생각해 볼 점

1. 진짜 어려웠다. level4 문제를 정말 오랜만에 풀어봤다. 그래도 정답을 찾아보지 않고 직접 생각해서 풀어서 성취감을 느낄 수 있었다.
2. 마지막에 unordered_set으로도 시간초과가 나서 공간복잡도를 생각한 뒤, 2차원 배열로 바꾼게 효과적이었다. unordered_set 이 hash를 사용해서 일반 map보다 검색 속도가 빠르다고 하더라도, 굳이 int,int를 string으로 바꾸기보다, 2차원 배열로 직접 접근하는게 훨씬 빨랐다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL