알고리즘/programmers

[Programmers] 최고의 집합

꾸준함. 2022. 6. 21. 08:47

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12938

 

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

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

programmers.co.kr

집합의 원소 간의 차가 최소일 때 각 원소 간의 곱이 최대가 되는 것은 자명합니다.

 

따라서, 알고리즘은 아래와 같습니다.

1. s를 n으로 나누었을 때 1보다 작을 경우 원소들의 합이 s가 될 수 없으므로 바로 -1을 반환해줍니다.

2. 우선, 벡터에 (s / n)을 n개 넣어줍니다.

2.1 여기서 (s / n)은 s를 n으로 나누어준 후 소수점 이하 값들을 버린 값입니다.

3. 2.1에서 언급했듯이 소수점 이하 값들을 버렸으므로 (s / n) * n을 할 경우 s보다 작을 수 있으며 해당 값을 k라고 하겠습니다.

3.1 (s - k)만큼 벡터 내 원소들을 선정해 1씩 증가시키면 집합의 원소 간의 차가 최소가 되므로 각 원소 간의 곱이 최대가 됩니다.

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~

반응형

'알고리즘 > programmers' 카테고리의 다른 글

[Programmers] 불량 사용자  (0) 2022.06.25
[Programmers] 선입 선출 스케줄링  (0) 2022.06.21
[Programmers] 야근 지수  (0) 2022.06.21
[Programmers] 가장 긴 팰린드롬  (0) 2022.06.21
[Programmers] N-Queen  (0) 2022.06.14