[25.03.10] algo 백준 30618 리뷰

25.03.10(Thu) 알고리즘 스터디 리뷰

문제 요약

donstructive

• 순열의 점수 = 모든 연속 부분 수열의 합의 총합
• 위치 i의 숫자는 i×(N-i+1)개의 부분 수열에 등장함
• 가중치가 높은 위치에 큰 숫자를 배치하면 최대 점수 달성

풀이방식

수열의 점수의 가중치 풀이방식
수열의 점수가 가장 많이 나오기 위해서는 수열을 구성할때 많이 들어가는 위치에 최대한 큰수를 구성하는 방식으로 풀이해야 했다. 그래서 처음으로 생각했던 부분은 가중치 배열을 생성하고 가중치가 큰 순서대로 순열을 구성하는 방식이였다. 그런데 왜 인지 모르겠지만 풀이 과정에서 틀린 부분이 있었는지 통과하지 못했다.

홀수와 짝수로 나눠서
다른 사람들의 풀이를 참고했을때 이 방식이 가장 보편적인 방식인거 같았다. 홀수와 짝수로 나누어서 가운데에 가장 큰수를 놓도록 채워가는 방식이였다. 홀수와 짝수로 나누어서 생각하는 방식은 패턴을 판단하는 과정을 넘기고 실제 패턴을 반복문으로 풀어내기만 하면 되는 방식이였다…

**이런 패턴을 파악할때 직접 구현할 수 있는지와 판단하는 과정까지를 구현해야 할지를 잘 생각해보고 풀이하는 과정이 필요할 것 같다.

결과 코드