Greedy 문제는 특별한 방식이 있기보다는 그리디 문제임을 확인하고, 문제를 최적화할 수 있는 우선 순위를 찾는 것이 필요하다고 생각한다. 최적화이기 때문에 모든 문제에 범용적으로 적용되는 것은 아니고, 문제마다 최적화할 수 있는 방안을 빨리 캐치하는 것이 필요하다. 이때 직관을 요구한다고 생각한다.
문제를 풀이하기 위한 아이디어를 간략하게 정리해보겠다.
1541. 잃어버린 괄호
1541번: 잃어버린 괄호
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다
www.acmicpc.net
적당히 괄호를 쳐서 식의 최솟값을 구하는 것이다.
예를들어, 55-50+40이 있다.
당연히 55-(50+40) 으로 하면 가장 작은 수가 나옴을 확인할 수 있다.
그럼 경우의 수를 생각해서, 여기저기 괄호로 감싸면서 최댓값을 찾아야할까?
NO!!!!🙅♀️💥
일단 직관으로 가장 + 연산자들을 먼저 계산한다.
그리고 남은 - 연산들을 수행하면 된다.
코드로 구현하면 다음과 같다.
from sys import stdin as s
import sys
expression = s.readline().split('-')
# + 연산으로 split된 것끼리 더하기
for i in range(0, len(expression)):
expression[i] = sum(list(map(int, expression[i].split('+'))))
result = expression[0]
# 맨 앞에 있는 원소부터 하나씩 빼기
for i in range(1, len(expression)):
result -= expression[i]
print(result)
1946. 신입 사원
1946번: 신입 사원
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성
www.acmicpc.net
신입 사원은 서류와 면접으로 평가받는다. 지원자는 합격하기 위해 적어도 하나는 다른 지원자보다 떨어지지 않아야 한다.
- 일단 서류 심사 결과로 정렬한다.
2 3
4 1
5 5
3 2
1 4 - 서류 결과가 i번째 사람에 대해 0부터 i-1번째인 사람들의 면접 심사 결과보다 높다면, 합격이다.
- i-1번째 사람보다 면접 심사 결과가 높은 사람의 면접 순위를 저장하다.
- i번째 사람들의 면접 성적 순위가 가장 높은 사람의 순위와 비교한다. 그 사람보다 높다면, 합격이고 그렇지 않다면 탈락이다.
(이미 서류가 다른 앞선 지원자들보다 낮기 때문에)
- i번째 사람들의 면접 성적 순위가 가장 높은 사람의 순위와 비교한다. 그 사람보다 높다면, 합격이고 그렇지 않다면 탈락이다.
from sys import stdin as s
import sys
t = int(s.readline())
for i in range(t):
n = int(s.readline())
rank = []
for j in range(n):
rank.append(list(map(int, s.readline().split())))
rank.sort()
print(rank)
top = 0
result = 1
for i in range(1, n):
# i번째 사람에 대해서 0~i-1 번째 사람들과 면접 심사 결과를 비교했을 때, 더 높다면 채용이 된다.
if rank[i][1] < rank[top][1]:
# 모든 사람과 비교하는 것은 시간이 많이 들기 때문에, 가장 높은 사람의 순위랑 비교한다.
top = i
result += 1
print(result)
1700. 멀티탭 스케쥴링
1700번: 멀티탭 스케줄링
기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전
www.acmicpc.net
역시 우선 순위를 두고 행동한다.
우리가 직접 행동한다고 생각해보자.
- 빈 자리가 있으면 꽂을 것이다.
- 꽂아야 하는 멀티탭이 이미 꽂혀있다면, 그냥 둘 것이다.
- 멀티탭을 뽑아야 한다.
- 앞으로 쓰지 않을 것이라면 그냥 뽑는다.
- 가장 나중에 쓰일 것 먼저 뽑는다.
이제 이것을 코드로 구현하면 Simple(?)😎
from sys import stdin as s
import sys
n, k = map(int, s.readline().split())
items = list(map(int, s.readline().split()))
answer = 0
plugin = []
def check(i):
target = 0
idx = -1
for p in plugin:
# i 이후에 안쓰인다면 뽑는다.
if p not in items[i:]:
return p
# 인덱스로 어디 위치에 있는지 확인한다.
if idx < items[i:].index(p):
target = p
idx = items[i:].index(p)
return target
for i in range(k):
# 아이템을 꽂을 수 있는 자리가 있다면
if len(plugin) < n:
# 아이템이 있다면 추가하지 않는다.
if items[i] in plugin:
continue
# 아이템이 없다면 추가한다.
else:
plugin.append(items[i])
# 아이템을 꽂을 수 있는 자리가 없다면 -> 빼고 꽂아야 한다.
# 앞으로 쓰이지 않는다면 뽑는다.
# 가장 나중에 쓰이는 것을 뽑는다.
if not items[i] in plugin:
plugin[plugin.index(check(i))] = items[i]
answer += 1
print(answer)
Reference
