📌 문제 035) 회의실 배정하기
시간 제한 2초, 실버 I, 백준 1931번
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작 시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 (2^31)-1보다 작거나 같은 자연수 또는 0이다.
11 # 회의 개수 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
4
1단계 문제 분석
- 1개의 회의실에 회의가 겹치지 않게 최대한 많은 회의를 배정해야 한다.
- 그리디 알고리즘을 적용해야 한다.
- 현재 회의 종료 시간이 빠를 수록 다음 회의와 겹치지 않게 시작하는 데 유리하다.
- 종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의실을 적절하게 선택하면 해결할 수 있다.
- 회의 정보와 관련된 데이터를 저장한 후 종료 시간 순으로 정렬한다. 단, 종료 시간이 같은 경우에는 시작 시간을 기준으로 다시 한번 정렬한다.
- 순차적으로 탐색하다가 시간이 겹치지 않는 회의가 나오면 선택한다.
2단계 슈도 코드
N(회의 개수) A(회의 정보 저장)
A 리스트 정렬 수행 # 종료 시각 기준으로 정렬, 종료 시각이 같으면 시작 시각 기준 정렬
for 회의실의 개수만큼 반복:
if 앞 회의의 종료 시각보다 시작 시각이 늦은 회의가 나온 경우:
현재 회의의 종료 시각으로 종료 시각 업데이트
진행할 수 있는 회의 수 1 증가
총 진행 가능 회의 수 출력3단계 코드 구현
N = int(input())
A = [[0] * 2 for _ in range(N)]
for i in range(N):
S, E = map(int, input().split())
A[i][0] = E # 종료 시각 우선 정렬이 먼저이므로 0번째에 종료 시각을 먼저 저장
A[i][1] = S
A.sort()
count = 0
end = -1 # 초기값을 -1로 설정하면 첫 번째 회의는 언제나 배정 가능하도록 한다.
for i in range(N):
# 현재 검사하고 있는 회의의 시작 시각이 현재까지 배정된 회의의 종료 시각보다 뒤에 있다면,
# 회의를 배정할 수 있다.
if A[i][1] >= end: # 겹치지 않는 다음 회의가 나온 경우
end = A[i][0] # 종료 시각 업데이트
count += 1
print(count)📌 문제 036) 최솟값을 만드는 괄호 배치 찾기
시간 제한 2초, 실버 II, 백준 1541번
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
55-50+40
출력
첫째 줄에 정답을 출력한다.
-35
1단계 문제 분석
- 그리디의 관점에서 생각하면 쉽게 풀 수 있다.
- 가장 작은 최솟값을 만들기 위해서는 가능한 한 큰 수를 빼야 한다.
- 수식이 더하기와 빼기 연산만으로 이뤄져 있기 때문에 더하기에 해당하는 부분에 괄호를 쳐서 먼저 모두 계산한 후 빼기를 실행하면 문제가 해결된다.
- 가장 먼저, 더하기 연산을 실행한다.
- 가장 앞에 있는 값에서 더하기 연산으로 나온 결괏값들을 모두 뺀다.
2단계 슈도 코드
answer(정답 변수)
A 리스트(들어온 데이터를 "-" 기호를 기준으로 split)
# 현재 String에 있는 수를 모두 더하는 함수 구현
mySum():
현재 들어온 String 값을 "+" 기호 기준으로 split() 수행
for 나뉜 데이터 개수만큼 반복:
String 값을 Integer 형으로 변환해 리턴값에 더하기
전체 합 리턴
for i를 A만큼 반복하기
결괏값 = mySum(A[i]) 함수 수행하기
if 가장 앞 데이터일 때:
answer에 결괏값 더하기
else:
answer에 결괏값 빼기
answer 출력3단계 코드 구현
answer = 0
A = list(map(str, input().split("-")))
def mySum(i): # -로 나뉜 그룹들의 합을 구하는 함수
sum = 0
temp = str(i).split("+")
for i in temp:
sum += int(i)
return sum
for i in range(len(A)):
temp = mySum(A[i])
if i == 0:
answer += temp # 가장 앞에 있는 값만 더하기
else:
answer -= temp # 뒷부분의 값은 합쳐서 빼기
print(answer)