프로그래머스. 최고의 집합

티스토리 뷰

tose33 2022. 2. 8. 21:21

코딩테스트 연습 - 최고의 집합

자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만

programmers.co.kr

집합 원소들의 합이 같을 때, 곱이 가장 큰 경우는 언제일까?

모든 원소들의 차가 최소일때 곱이 가장 크다.

n=2, s=9일때 집합은 {1,8}, {2,7}, {3,6}, {4,5}가 있는데 각각의 곱은

{1,8} = 8, {2,7} = 14, {3,6} = 18, {4,5} = 20으로 원소들의 차가 가장 작을때 곱이 가장 크다는것을 알 수 있다.

그럼 answer 벡터에는 s / n 값을 최대한 채워넣고 남는 값은 각 원소에 1씩 나눠서 분배해주면 된다.

공지사항

최근에 올라온 글

최근에 달린 댓글

링크

글 보관함