백준 1744번 수 묶기

요구사항 정의

• 두 수를 묶거나 더하면서 합이 최대가 되도록 하기
• 위치에 상관없이 묶을 수 있음

제약 조건

• 0 < N < 50
• 정답은 2^31보다 작다

풀이 방법

이 문제에서 고민했던 부분은 음수를 어떻게 처리할지였다.

나는 오름차순 정렬 후 DP를 사용하는 방식으로 풀었는데,
다른 풀이를 보니 양수와 음수를 분리해 각각 계산한 뒤 합치는 방법도 있었다.

 

두 방식 모두 가능한 접근이지만,
정렬 후 DP로 푸는 쪽이 실수할 여지가 적고 구현이 직관적이라고 느꼈다.

나는 각 단계에서

• 더했을 때의 최댓값
• 곱했을 때의 최댓값

을 각각 저장했고,
마지막에는 이 두 값 중 더 큰 값을 정답으로 선택했다.

 

 

코드