[2025 1학기 알고리즘 스터디] 이서영 #3주차
*파이썬으로 풀었습니다.
- 1931 : 회의실 배정
- 1541 : 잃어버린 괄호
- 11047 : 동전 0
1931. 회의실 배정
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
회의를 최대한 많이 하려면 '빨리 끝나는 것 중에서 골라내면 되겠다.' 라는 생각을 하고 문제로 들어갔습니다.
import sys
input = sys.stdin.readline
N = int(input()) #회의 수
timeLine = [list(map(int,input().split())) for _ in range(N)] #회의 모음
seq = sorted(timeLine, key = lambda x : x[1]) #끝나는 시간 기준으로 정렬
meeting = []
meeting.append(seq[0])
for i in range(1,N):
if seq[i][0] >= meeting[-1][1]:
meeting.append(seq[i])
else:
continue
print(len(meeting))
먼저 sorted를 이용하여 회의가 끝나는 시간 순서대로 정렬된 리스트(seq)를 만들어주었습니다.
그 다음 기준에 만족할 시간들을 골라내기 위해 meeting이라는 새로운 리스트를 만들고
어차피 젤 먼저 끝나는 건 꼭 있어야 하니 meeting에 seq[0]을 추가해주었습니다.
반복문으로 조건에 맞는 시간만 meeting에 추가하고 meeting 요소 개수 출력하면 정답!
틀린 이유
-> 정렬 할 때 끝나는 시간이 같을 때를 고려 안 함
3
2 3
1 3
3 3위에 처럼 입력 되었을 때 방금 작성한 seq는 정렬 시 오직 끝나는 시간만 기준으로 정렬하기에
아래처럼 정렬 되게 됩니다.
끝나는 시간이 같을 때 시작 시간이 늦는 회의를 먼저 선택할 수 있게 되어서 시작시간도 정렬기준에 포함해주어야 합니다.
import sys
input = sys.stdin.readline
N = int(input()) #회의 수
timeLine = [list(map(int,input().split())) for _ in range(N)]
seq = sorted(timeLine, key = lambda x : (x[1],x[0])) #시작시간도 정렬
meeting = []
meeting.append(seq[0])
for i in range(1,N):
if seq[i][0] >= meeting[-1][1]:
meeting.append(seq[i])
else:
continue
print(len(meeting))
1541. 잃어버린 괄호
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
-> -가 나오면 무조건 괄호 쳐서 다른 -나올 때까지는 계속 괄호 안으로
라는 생각을 했지만 이걸 어떻게 구현하지????
처음과 마지막 문자는 숫자이니 -를 기준으로 분류 해주고
안의 식들을 더한 값을 저장하는 리스트를 새로 만들어 인덱스 0부터 차례대로 빼주는 식으로 했습니다.
import sys
input = sys.stdin.readline
ex = input().split('-')
plus = []
for i in range(len(ex)):
x = eval(ex[i])
plus.append(x)
min = plus[0]
for i in range(1, len(plus)):
min -= plus[i]
print(min)
바로 반례 출현
파이썬에서 앞에 0이 붙은 10진수 정수는 허용이 되지 않는다고 합니다.
eval로 꿀빨려하지말고 천천히 해줍니다.
import sys
input = sys.stdin.readline
ex = input().split('-')
plus = []
for i in range(len(ex)):
x = ex[i].split('+') #+로 구분
n = 0
for j in range(len(x)):
n += int(x[j])
plus.append(n)
min = plus[0]
for i in range(1, len(plus)):
min -= plus[i]
print(min)
11047. 동전 0
문제
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
백준에서 문제랑 입력을 복붙하면 똑같이 크게 되네요 신기
-> 오름차순으로 주어지니까 차례대로 입력받은 거 리스트로 만든 후, 동전의 가치들 중 K보다 작은 거부터 차례대로 하면 될 거 같은데라는 생각을 했습니다. 예제에는 1 5 10 50 이런 간단한 숫자로만 가치로 되어있었지만 1 2 4 8 이런 것도 되지 않나 라는 생각도 들었지만 1원 있으니 어떻게든 되겠지..
import sys
input = sys.stdin.readline
N, K = map(int,input().split())
coinValue = list(int(input()) for _ in range(N))
start = -1
result = 0
for i in range(N): #시작 인덱스 찾기
if coinValue[i] == K:
result = 1 #같으면 걍 1로 끝남
break
elif coinValue[i] < K:
start = i #작을 때마다 계속 갱신
else:
break #커지면 끝
x = K #연산을 위해서
for i in range(start, -1, -1):
result += x // coinValue[i]
x = x % coinValue[i]
print(result)시작 인덱스를 찾은 후 계속 반복해서 result에 추가하는 식으로 해주었습니다.
시작 인덱스를 찾을 때, 동전의 가치와 K가 같으면 result를 1로 해놓고 프로그램 종료를 안 했어서 틀렸습니다..
import sys
input = sys.stdin.readline
N, K = map(int,input().split())
coinValue = list(int(input()) for _ in range(N))
start = -1
result = 0
for i in range(N): #시작 인덱스 찾기
if coinValue[i] == K:
result = 1 #같으면 걍 1로 끝남
print(result)
sys.exit()#아예 끝내기
elif coinValue[i] < K:
start = i #작을 때마다 계속 갱신
else:
break #커지면 끝
x = K #연산을 위해서
for i in range(start, -1, -1):
result += x // coinValue[i]
x = x % coinValue[i]
print(result)젠장~
그리디 후기는 1주차 2주차 때와는 다르게 뭔가 공식같은 게 없는 느낌입니다. 그래서 문제 푸는 방법을 생각하는 것은 쉬웠어요. 쉽지만 저런 디테일이 필요한 부분에서 계속 틀려서 이런 거 확인하는 게 어려운 것 같습니다. 그래도 저저번 저번보다는 상대적 힐링