[알고리즘] 그리디 - 1417 1758 27446 2777 17392 11000

그리디 알고리즘

Greedy = 탐욕

말 그대로 각 단계에서 가장 욕심을 부려서 최선의 선택을 하는 것

근데 이게 결과적으로 최선의 선택으로 통하는 경우 / 통하지 않는 경우가 있다.

당연히 그리디 알고리즘은 이 탐욕법이 통하는 문제에 쓰는 것

 

1417 국회의원 선거

 

오랜만에 알고리즘 하니까 머리가 안돌아간다...

A = 다솜, B, C 총 3명의 후보가 있다 치고,

A: 5, B: 7, C: 7

A+B+C = 19, 19/3 = 6.xxx.... 대충 반올림하면 7 이고 -5 하면 2

이렇게 생각해봤다

(사실 더 생각하기 귀찮았다)

근데 후보 1명이면 어칼려고....... 당연히 틀렸다.

그래서 다시 생각을 해봤다.

 

A 기준 B, C 를 정렬하면 5 < 7, 7

한명을 매수하면 6 | 6, 7

다시 정렬하면  6  < 7, 6

그러면 또 한명을 매수하면

7 > 6, 6

 

while 문으로 정렬을 계속 돌려주고,

A보다 크면 1씩 빼준 후 A에게 더해주다가

맨 앞 숫자가 A보다 작으면 루프 종료

 

N = int(input())

dasom = int(input())

others = []

for _ in range(1, N):
    others.append(int(input()))

ans = 0 
   
if N == 1:
    ans = 0
else:
    others.sort(reverse=True)
    while others[0] >= dasom:
        others[0] -= 1
        dasom += 1
        ans += 1
        others.sort(reverse=True)
        
print(ans)

 

 

1758 알바생 강호

팁 = 원래 주려고 생각했던 돈 - (등수 - 1)

손님의 수를 바꿨을 때 팁의 최댓값 구하기

 

3원, 2원, 1원을 주고싶어함 -> 위에 문제랑 비슷한듯??

일단 3원 받아 -> 그럼 다음에 받을 수 있는 팁은 자동으로 1이 빠진 1원 0원 -> 일단 1원 받아 -> 또 1이 빠진  => 0원 끝

 

위 문제에서 정렬을 max 로 바꾸면 거의 비슷함

 

N = int(input())
tips = [0] * N
for i in range(N):
    tips[i] = int(input())
ans = 0
while max(tips) > 0:
    ans += max(tips)
    tips.remove(max(tips))
    tips = [x-1 for x in tips]
    
print(ans)

근데 시간 초과 떴다ㅏㅏㅏㅏㅏㅏㅏㅏㅏ max 시간복잡도가 O(n)이라 반복문 돌면서 돌아버린거같다

 

그래서 그냥 정렬 한번 하는걸로 결정했다

 

N = int(input())
tips = [0] * N
for i in range(N):
    tips[i] = int(input())
ans = 0
tips.sort(reverse = True)
loop = 1

for i in range(len(tips)):
    if (tips[0] - (loop - 1) > 0) > 0:    
        ans += tips[0] - (loop - 1)
        tips.pop(0)
        loop += 1
    
print(ans)

 

 

27446 랩실에서 잘 자요

창조공포 가득한 문제다... 쫄려서 머리가 안돌아가더라

 

n,m = map(int, input().split())
pages = list(map(int, input().split()))
pages = list(set(pages))
pages.sort()
ink = 0
all_pages = [i for i in range(1, n+1)]

to_print = set(all_pages) - set(pages)
to_print = list(to_print)
to_print.sort()
pointer = 0

while pointer <= len(to_print)-1:
  prev_pointer = pointer

  if pointer != len(to_print)-1:
    while (to_print[pointer+1] - to_print[pointer]) < 4:
      pointer += 1

      if pointer == len(to_print)-1:
        break

  ink += 5 + 2*(to_print[pointer] - to_print[prev_pointer]+1)
  pointer += 1
  
print(ink)

 

뭔가 포인터 개념이 갑자기 생각나서 한번 써봤는데 이렇게 쓰는게 아닌 것 같지만.. 우선 맞았으니 코드는 첨부한다.

페이지 사이의 거리가 4 이상이면 따로 출력하고, 그 밑이면 한번에 출력하는 방법으로 코드를 작성했다.

 

2777 숫자 놀이

 

개인적으로 좀 어려웠던 문제다.

인수를 찾아낸 후에 10 밑의 인수들로만 이루어지도록 해서 숫자를 만들어야 된다는 생각만 들어서 코드 흐름이 감이 오질 않아 다른 분들의 코드를 참고해서 풀었다. 생각해보니까 몇 자리 수인지만 구하면 되는건데 내가 너무 복잡하게 생각했다.

t = int(input())
numbers = [9,8,7,6,5,4,3,2]
results = []

for _ in range(t):

  n = int(input())
  nums = []
  tmp = n

  while True:
    cnt = 0
    if tmp == 1:
      nums.append(1)
      break       # n이 1이면 1이 답이니까 그대로 break
    for s in numbers:
      if tmp%s == 0:  # 2~9중 9부터 나눠본다 나눠지면 인수이므로 nums 배열에 저장
        nums.append(s)
        tmp /= s
        break
      cnt += 1

    if cnt == 8:
      if tmp >= 10: #계속 나눴는데도 10 이상이라면 빠져나와서 -1을 답으로 결정
        break
    if tmp == 1: # 완전히 나누어 떨어지니까 나
       break
  if cnt == 8:
    results.append(-1)
  else:
    results.append(len(nums))


for i in range(len(results)):
  print(results[i])

 

 

17392 우울한 방학

인호는 인싸인듯 하다.

약속이 없는 날은 어제의 기분 - 1

인호의 약속 개수가 3, 방학일이 10일, 약속 각각의 행복이 2 2 1

우울을 최소화하는 것이 중요하므로 우울이 퐁당퐁당이 되어야 한다

약2 1 0 약2 1 0 약 1 0 최대 8일간 견딜 수 있으므로 우울을 그 사이에 하나씩 넣어주면 총 우울은 2가 된다.

이 흐름대로 작성한 코드는 다음과 같다.

n, m = map(int, input().split())

if n == 0:
  print(m**2)

else:
  happy = list(map(int, input().split()))

  not_gloomy = [x+1 for x in happy]

  if sum(not_gloomy) >= m:
    print(0)
  else:
    gloomy_days = m - sum(not_gloomy)
    if gloomy_days <= len(not_gloomy) + 1:
      print(gloomy_days)
    else:
      print(gloomy_days + 3*(gloomy_days - len(not_gloomy) + 1))

 

흠 근데 틀려서 다시 짜봄

우울 합을 잘못생각했따 20일 우울하면 400이 우울이 아니라 시그마 엑스제곱 1~20임 ㄷㄷ

하.. 이거땜에 별짓 다하느라 코드가 좀 꼬였는데 어쨌든 알아내서 해결했으니까..

수정한 코드는 다음과 같다.

n, m = map(int, input().split())
ans = 0
if n == 0:
  print(sum(x**2 for x in range(1, m+1)))

else:
  happy = list(map(int, input().split()))

  not_gloomy = [x+1 for x in happy]

  if sum(not_gloomy) >= m:
    print(0)
  else:
    gloomy_days = m - sum(not_gloomy)
    if gloomy_days <= len(not_gloomy) + 1:
      print(gloomy_days)
    else:
      blanks = len(not_gloomy) + 1
      blank_list = [gloomy_days // blanks] * blanks 
      tmp = gloomy_days % blanks

      while tmp > 0:
        for i in range(len(blank_list)):
          if tmp == 0:
            break
          tmp -= 1
          blank_list[i] += 1
      for x in blank_list:
        for i in range(1, x+1):
          ans += i**2
      print(ans)

 

11000 강의실 배정

 

 

최대한 숫자가 이어지게 짜면 된다

import sys
input = sys.stdin.readline

n = int(input())
classes = [[]]*n
ans = n
for i in range(n):
  classes[i] = list(map(int, input().split()))

classes.sort(key = lambda x: (x[1], x[0])) #끝나는 시간이 이르고, 이후 시작 시간이 이른 순으로 정렬

for i in range(len(classes)):
  end_time = classes[i][1]
  for j in range(i+1, len(classes)):
    start_time = classes[j][0]
    if end_time > start_time:
      continue
    else:
      ans -= 1

print(ans)

 

시간초과가 뜰 거 같았는데 역시였다

힙큐 잘 못해서 안썼는데 써야겠다는 생각이 정말 강하게 들어서 코드를 새로 수정했다.

import sys
import heapq
input = sys.stdin.readline

n = int(input())
classes = []
number = []
for _ in range(n):
  classes.append(list(map(int, input().split())))

classes.sort()
heapq.heappush(number, classes[0][1]) #힙(넘버)에 끝나는시간을 넣어

for i in range(1, n):
  if classes[i][0] < number[0]: # 만약에 클래스의 시작시간이 끝나는시간보다 작아
    heapq.heappush(number, classes[i][1]) # 넘버 힙에 끝나는 시간도 넣어
  else: # 만약에 클래스 시작시간이 현재 들어있는 끝나는 시간보다 커
    heapq.heappop(number) # 힙에서 빼
    heapq.heappush(number, classes[i][1]) # 그리고 다음걸 넣어

print(len(number))

힙큐를 좀더 잘 써보면 코드 짜기가 쉬워질 것 같다.