그리디 알고리즘 - 탐욕적으로 생각하게 연습하기1(11508 2+1세일, 1789 수들의 합)

1. 문제1

 

11508번: 2+1 세일 (acmicpc.net)

11508번: 2+1 세일

 

주어진 유제품을 3개 단위로 살때, 3개중에서 가장 싼 것은 무료로 살 수 있다면 최소 비용으로 구매하는 방법은..?

 

2. 풀이1

 

최대한 비싼 가격들을 지불하지 않게하면 될것 같다

 

유제품 가격을 받아서 가장 비싼 가격으로 내림차순 정렬한 다음에 인덱스로 cost_list를 순회해서

 

3의 배수가 될때 반복문을 continue시키고 3의 배수가 아니면 cost에 더해주는 방식으로 하면 될 것 같다

 

from sys import stdin

n = int(stdin.readline())

cost_list = []

for _ in range(n):
    
    c = int(stdin.readline())

    cost_list.append(c)

cost_list.sort(reverse=True)

cost = 0

for i in range(1,n+1):
    
    if i % 3 == 0:
        
        continue
    
    else:
        
        cost += cost_list[i-1]

print(cost)

 

3. 문제2

 

1789번: 수들의 합 (acmicpc.net)

1789번: 수들의 합

 

서로 다른 n개의 자연수 합이 s인데, s를 알때 n의 최댓값을 구해본다면..?

 

4. 풀이2

 

최선의 해를 찾는다는 생각으로... 가장 많은 개수의 자연수를 더한다고 생각을 해본다면...

 

합이 일정하니까 최대한 작은 값들을 더해나가야 할것 같다

 

"서로 다른 n개의 자연수"니까 최대한 작은 값들을 더하는 방법은..?

 

1+2+3+4+5+... + n이겠지

 

그러면 이건 $\frac{n(n+1)}{2}$인데, 이것과 s가 서로 같게 되는 n을 구하면 될 것 같다

 

근데 당연하지만..

 

s=200이라면 n(n+1) = 400인데 이를 만족하는 자연수 n은 존재하지 않는다

 

그러니까 방정식의 해는 n = 19.xxxx...인데

 

이게 무슨 뜻일까?

 

-----------------------------------------------------------------------------------------------------

 

19개의 최소 자연수 합

 

1+2+3+4+5+6+...+19 = 190이잖아

 

하지만 20개의 최소 자연수 합

 

1+2+3+4+....+20 = 210이란 말이지

 

하지만 각 자연수 구성이 중요한게 아니고 "자연수 개수의 최댓값"이 중요하다

 

그러니까 1+2+3+4+5+6+...+19에서 19를 빼고 1+2+3+4+...+18 = 171에다가 29를 더하면 200이잖아

 

그래도 우리는 19개의 자연수를 사용한 것이란 말이지

 

하지만 20개를 쓰면 200을 무조건 넘어간다

 

최소의 자연수 20개만을 사용했는데도 210이니까

 

따라서 $\frac{n(n+1)}{2} <= s$를 만족시키는 최대의 자연수 n이 정답이다

 

그래서 방정식 $\frac{n(n+1)}{2} = s$의 해를 근의 공식으로 구해서

 

$ n = \frac{-1+\sqrt{1+8s}}{2} $는 자연수가 아닐 가능성이 높은데

 

n = 19.1234...라면 18개의 최소 자연수 1+2+...+18에다가 s가 되도록 어떤 자연수 a를 더하면 되니까 19가 정답

 

n = 36.2531...라면 35개의 최소 자연수 1+2+...+35에다가 s가 되도록 어떤 자연수 a를 더하면 되니까 36이 정답..

 

그래서 $ n = \frac{-1+\sqrt{1+8s}}{2} $에다가 int()를 취하면 정답이 될것이다

 

-----------------------------------------------------------------------------------------------------

 

from sys import stdin

s = int(stdin.readline())

answer = int((-1+(1+8*s)**(1/2))/2)

print(answer)