[5문제] 그리디 문제풀이 05

백준 15720번

해결 아이디어

각 제품의 가격을 리스트로 전달받아 오름차순 해준다. 가장 가격이 높은 버거, 사이드 메뉴, 음료부터 세트 메뉴로 만들어주면서 10% 할인을 해준다. 세트를 구성할 수 없는 남은 단품들은 슬라이싱을 통해 가격 할인 없이 추가를 해준다. 두 경우를 합해서 세트 할인이 적용된 후의 최소 가격을 구한다.

내가 작성한 코드

B, S, D = map(int, input().split(' '))

burgers = list(map(int, input().split(' ')))
sides = list(map(int, input().split(' ')))
drinks = list(map(int, input().split(' ')))

burgers = sorted(burgers, reverse=True)
sides = sorted(sides,reverse=True)
drinks = sorted(drinks,reverse=True)

set_count = min(B,S,D)
before_cost = sum(burgers[::]+sides[::]+ drinks[::])

set_cost = int(sum(burgers[:set_count]+sides[:set_count]+drinks[:set_count])* 0.9)
rest = sum(burgers[set_count:]+sides[set_count:]+drinks[set_count:])
min_cost = set_cost + rest

print(before_cost)
print(min_cost)

백준 19564번

해결 아이디어

입력받는 글 S 중에서 글자 순서가 알파벳 배열 순서와 같다면, 입력받는 횟수를 줄일 수 있다. 알파벳 전체를 문자열로 받을 때, S에서 현재 글자의 인덱스 값이 다음 글자의 인덱스 값보다 작다면 입력받는 횟수를 줄일 수 있다는 것이다. 예를 들어 'polymath'같은 경우, 'ly'와 'at'에서 입력받는 횟수를 줄일 수 있다.

내가 작성한 코드

alphabet = 'abcdefghijklmnopqrstuvwxyz'
words = input()

L = len(words)
count = 1

for i in range(L-1):
     
    if alphabet.index(words[i]) < alphabet.index(words[i+1]):
        continue
    else:
        count+=1

print(count)

백준 10610번

해결 아이디어

N을 입력받았을 때, 0이 존재하고, N의 각 자리 수의 합이 3의 배수이면 N을 30의 배수로 만들어줄 수 있다. 그렇지 않은 경우는 -1을 출력해준다. 이때 30의 배수가 되는 가장 큰 수는 N의 마지막 자리 수는 0으로 고정이 되니 N의 각 자리 수를 내림차순해주면 된다.

내가 작성한 코드

N = input()
L = len(N)

total_sum = 0
for i in range(L):
    total_sum += int(N[i])

if N.find('0')!= -1 and total_sum % 3 == 0:
    N = ''.join(sorted(N, reverse=True))
    print(N)
    
else:
    print(-1)

백준 1789번

해결 아이디어

서로 다른 N개의 자연수의 합일 때 N이 최댓값이 되려면 가장 작은 수인 1부터 순서대로 더해준다. n까지 더했을 때, S-(n(n+1)/2) 값이 n+1보다 작다면 n번이 N의 최댓값이다. 왜냐하면 이 시점에서S-(n(n+1)/2)이 n+1보다 작기 때문에 횟수를 추가할 수도 없으며, S-(n(n+1)/2)를 어떻게 분배해주더라도 이미 서로 다른 값들이기 때문이다.
즉, 1부터 n까지의 합이 S보다 커지기 전까지 계속해서 횟수를 더해준다. 반복문이 종료될 시점은 횟수가 N+1회일 때이므로 1을 빼준 값을 출력해준다.

내가 작성한 코드

S = int(input())
n = 1

while n * (n + 1) / 2 <= S:
    n += 1

print(n - 1)

백준 4796번

해결 아이디어

L은 P보다 작은 수 이다. 따라서 V를 P로 나눈 몫을 통해서 경고장 패턴동안 캠핑장을 이용할 수 있는 기간을 구할 수 있다. V를 P로 나눈 나머지를 통해 남은 기간동안 캠핑장을 이용할 수 있는 기간을 구할 수 있다.
하지만 남은 일 수가 L보다 클 경우에는 L이 남은 기간동안 캠핑장을 이용할 수 있는 기간이 된다. 이 조건도 활용해주어야 한다. 처음에는 그 조건을 생각하지 못해서 오답을 받았다.

내가 작성한 코드 -오답

i = 0
while True:
    i+=1
    L, P, V = map(int, input().split(' '))

    if L == P == V == 0:
        break
    
    else:
        
        n = V // P
        rest = V % P
        max_use = L * n + rest
        
        print('Case {} : {}'.format(i, max_use))

내가 작성한 코드

i = 0
while True:
  i+=1
  L, P, V = map(int, input().split(' '))

  if L == P == V == 0:
      break
  
  else:  
      n = V // P
      rest = V % P
      
      if L < rest:
          rest = L
          
      max_use = L * n + rest
      
      print('Case {}: {}'.format(i, max_use))