백준 1931 2217

1. 백준 1931 회의실 배정

 

def greed( lst ):

    lst = sorted(lst, key=lambda a: a[0])
    lst = sorted(lst, key=lambda a: a[1])
    last = 0
    cnt = 0


    for i, j in lst:
        if i >= last:
            cnt += 1
            last = j

    return cnt


if __name__ == '__main__':
    num = int(input())

    conference = []

    for i in range(num):
        conference.append(list(map(int, input().split())))
    print(greed(conference))

 

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

해결방안

sort를 활용하여 문제를 풀어내는 방식이다. 먼저 해당 문제는 최대한 많은 회의가 진행되어야 하기 떄문에 , End time 이 가장 빠른 회의를 select, 해당 회의를 진행토록 한다. 그리고 또한가지 고려해야 할 점은, 이전 회의의 Endtime 보다 해당 회의의 Start_time 이 빨라야 한다는 것이다. 

해당 점을 고려하여 먼저, 무작위로 입력된 회의 시간을 Start time 기준으로 정렬, 이후 정렬된 list를 End time 기준으로 정렬해 준다. 

 

이를 통해 End time 기준으로 정렬 된 list 속에 Start time 기준으로 정렬된 값들을 확인 할 수 있을 것이다. 

 

 

 

2. 백준  2217 로프 최대값 추정 

 

 

import sys


def greed(lst, k):
    lst.sort()

    new_min = []
    for i in lst:
        new_min.append(i * k)
        k = k - 1
    m = max(new_min)
    return m


if __name__ == '__main__':
    N = int(sys.stdin.readline())
    max_lst = []
    for i in range(N):
        max_lst.append(int(sys.stdin.readline()))
    print(greed(max_lst, N))

 

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

 

해결방안

가장 처음으로 짠 알고리즘은 방식은 맞았으나 시간초과 문제가 발생하였다. 해당 문제는 if를 for문에서 반복적으로 실행되어 컴파일 속도를 늦춘다는 단점에서부터 비롯되었다.  이러한 문제를 해결하기 위하여 먼저 list를 새로 생성, 각 로프 조합별 최고 길이를 모두 구하였다. 이후 이중 가장 최대값을 도출하여 반환하는 방식을 사용하였다. 

 

** for 문에서 반복적으로 if 문을 사용하는 것은 많은 컴퓨팅 파워를 활용하기에, 조금 두려워 해야 할 필요가 있다.**