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

백준 2217번

해결 아이디어

로프를 병렬로 연결하게 되면 w/k만큼 각각 중량이 걸리게 된다. 즉, 로프가 버틸 수 있는 최대 중량은 병렬로 연결하는 k개 로프 중에서 가장 작은 질량을 버틸 수 있는 로프 * 연결된 로프의 개수이다. 따라서 입력받은 로프를 내림차순 해준 후, 연결된 로프의 개수와 곱하여 가장 큰 값을 출력하도록 하였다.

내가 작성한 코드

n = int(input())

rope = [int(input()) for _ in range(n)]
rope = sorted(rope ,reverse =True)

for i in range(n):
    rope[i] = rope[i] * (i+1)

print(max(rope))

백준 1049번

해결 아이디어

각각의 경우를 나누어서 생각했다. 우선적으로 패키지 가격이 한 줄 가격으로 6개보다 가격이 낮은 경우, 그 조건 안에서 기타줄의 개수가 6개보다 작을 때와 그렇지 않은 경우를 판단한다.
조건1) 6개보다 작을 때, 패키지의 가격이 n x 한 줄 가격보다 낮다면 패키지 가격을 추가해주고, 그렇지 않을 경우에는 한 줄 가격을 추가해준다.
조건2) 패키지의 가격이 n x 한 줄 가격보다 높은 경우에는 한 줄 가격으로 추가해준다.
조건3) 기타줄이 6개보다 클 경우에는 패키지 가격으로 추가해준다.
조건4) 패키지 가격이 한 줄 가격으로 6개보다 가격이 높은 경우, 한 줄 가격으로 추가해준다.

내가 작성한 코드

n,m = map(int, input().split())
cost = [list(map(int,input().split())) for _ in range(m)]
result = 0
package_pay = min(cost, key = lambda x: x[0])[0]
each_pay = min(cost, key = lambda x: x[1])[1]

while n > 0:
    if package_pay < each_pay * 6:
        if n < 6:
            if package_pay < each_pay * n:
                result+= package_pay
                n-=6
            else:
                result+=each_pay
                n-=1
        else:
            result+= package_pay
            n-=6
    else:
        result+= each_pay
        n-=1

print(result)

백준 1449번

해결 아이디어

파이프의 왼쪽부터 물이 새는 곳을 막아주는 방법으로 테이프의 개수를 계산했다. 오름차순으로 정렬해준 후, 좌우 0.5 간격까지 생각해주어야 하므로 물이 새는 곳의 위치의 차에 1을 더한 길이가 테이프 길이보다 작다면 테이프를 추가해주는 것으로 문제를 해결할 수 있었다.

내가 작성한 코드

n,l = map(int, input().split())
location = sorted(list(map(int,input().split())))
tape = 1
start = location[0]

for i in range(len(location)):
    if abs((location[i]-start)) + 1 > l:      
        tape+=1
        start = location[i]

print(tape) 

백준 1541번

해결 아이디어

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 경우는 +연산자로 계산하는 부분을 모두 괄호를 쳐서 빼주면 된다.

내가 작성한 코드

expression = input().split('-')
num = []

for i in expression:
    result=0
    seperate = i.split('+')
    for j in seperate:
        result += int(j)
    num.append(result)
  
total_result = num[0]
for i in range(1, len(num)):
    total_result -= num[i]

print(total_result)

백준 1931번

해결 아이디어

회의실 배정을 할 때, 우선적으로 회의 시간이 가장 빠른 시간부터 정렬한 다음, 회의 시간이 가장 일찍 끝나는 시간으로 정렬해준다. 그 후, 회의가 마치는 시간이 다음 회의 시간이 시작하는 시간과 비교했을 때, 빠르거나 같다면 다음 회의 시간대로 넘겨주며 반복해준다.

처음 문제를 접했을 때, 시간 초과가 떴는데, 정렬해놓은 상태임에도 이중for문을 통해서 모든 경우를 다 돌려보려고해서 시간이 초과된 것 같았다.

내가 작성한 코드 - 시간 초과

n = int(input())
conference =[]
num_conference=[]
for i in range(n):
    schedule = tuple(map(int, input().split()))
    conference.append(schedule)
conference= sorted(conference)

for i in range(len(conference)):
    count = 1
    finish = conference[i][1]
    for j in range(len(conference)):
        if finish <= conference[j][0]:
            finish = conference[j][1]
            count+=1
    num_conference.append(count)
        
print(max(num_conference)) 

내가 작성한 코드

import sys

n = int(sys.stdin.readline())

conference =[]

for i in range(n):
    schedule = tuple(map(int, sys.stdin.readline().split()))
    conference.append(schedule)
conference = sorted(conference, key=lambda x: (x[1], x[0]))

count = 1
finish = conference[0][1]
for i in range(1,len(conference)):
    if conference[i][0] >= finish:
        count+=1
        finish = conference[i][1]

print(count)