수 묶기

• Prob
• Solv
• Check
• Feedback
• Ref

수 묶기

Prob

길이가 N인 수열의 위치에 상관없이 두 수를 묶어서 곱한 후 합한 최댓값
수열이 {0, 1, 2, 4, 3, 5}
0 + 1 + 2 + 4 + 3 + 5 = 15
0 + 1 + (2 * 3) + (4 * 5) = 27

Solv

1. dfs, bfs
   시간초과
2. dfs - sort + prunning
   양수부분과 음수부분 정렬을 반대로 해주어야해서 실패
3. 조건 분기
   • 양수 내림차순 정렬 후 1이 아니면 묶어서 곱하기 반복
     1이면 더하기
   • 음수, 0 오름차순 정렬 후 0이 아니면 묶어서 곱하기 반복
     음수가 홀수면 나머지 한 개를 0과 곱하기

Check

Feedback

dfs, bfs가 편하긴하지만 메모리 측면에서 비효율적이다. prunning을 성공 못하여 아쉽다. 조건 분기 하나하나 생각하기 정말 까다롭다.

Ref