01-5. 그리디 알고리즘 문제풀이

📝문제1. 백준 5585번

- 문제

https://www.acmicpc.net/problem/5585

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

입력
입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

출력
제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

예제 입력 1 : 380
예제 출력 1 : 4

예제 입력 2 : 1
예제 출력 2 : 15

- 나의 코드💻

n = int(input())
money = [500, 100, 50, 10, 5, 1]
changes = 1000 - n

count = 0
for i in money:
    if changes == 0:
        break
    count += changes // i
    changes %= i

print(count)

- 과정📖

어제 문제2번인 백준 2839번과 비슷한 문제인 것 같다. 거스름돈 개수가 가장 적게 잔돈을 주도록 하기 위해 500엔, 100엔, 50엔, 10엔, 5엔, 1엔을 높은 순서대로(내림차순) 배열에 넣어서 문제를 풀었다. 아직 이런 가장 적은 동전을 주기 위한 문제가 낯선데, 몇 번 더 풀어보면 확실하게 감이 올 것 같다.

---

📝문제2. 백준 1541번

- 문제

https://www.acmicpc.net/problem/1541

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력
첫째 줄에 정답을 출력한다.

예제 입력 1 : 55-50+40
예제 출력 1 : -35

- 나의 코드💻

- 정답 코드💻

alist = input().split('-')

sum = 0
for i in alist[0].split('+'):
    sum += int(i)

for i in alist[1:]:
    for k in i.split('+'):
        sum -= int(k)

print(sum)

- 비교 분석📖

55-50+40 이 식을 어떻게 입력받을지에 대한 아이디어를 떠올리지 못했다. -를 기준으로 괄호를 쳐야 한다는 것까지는 생각했는데, 저 식을 한번에 입력받아야 한다고 생각해서 계속 헤맸던 것 같다. 또한 그 뒤의 구체적인 풀이방법을 생각해내지 못했다.

만일 100 - 40 + 20 - 10 + 30 이라는 식을 입력받았을 때,
'-' 를 기준으로 100 - (40+20) - (10+30) 이렇게 괄호를 치면 값이 최소가 된다.
그래서 입력을 받을 때 '-'를 기준으로 입력을 받아야 하고, 그러면 ['100', '40+20', '10+30'] 이런식으로 리스트에 저장이 된다.
100 - (40+20) - (10+30) 이렇게 계산을 하려면 우선 리스트의 0번째 원소를 계산한 뒤 sum에 넣어준다. 그 후 1번째 원소부터 끝까지 '+'를 기준으로 분리해 빼준다. -(a+b)는 결국 -a -b이기 때문이다.

---

📝문제3. 백준 1931번

- 문제

https://www.acmicpc.net/problem/1931

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

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

출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

- 나의 코드💻

- 정답 코드💻

n = int(input())
alist = []
for i in range(n):
    ilist = list(map(int, input().split()))
    alist.append(ilist)

alist = sorted(alist, key = lambda x: [x[1], x[0]])

count = 0
start = 0
for i in alist:
    if i[0] >= start:
        start = i[1]
        count += 1

print(count)

- 비교 분석📖

좀 많이 어렵게 느껴진 문제.. 일단 이해는 하긴 했는데 다시 나온다 해도 내가 혼자 풀 수 있을지 모르겠다. lambda 문법이 헷갈려서 계속 찾아봤다. 일단 원리를 이해하니 어떤 문제인지는 파악이 갔다. 혼자서도 원리를 파악할 수 있도록 더 노력해야겠다. 아직 모두 이해한 것은 아니라 좀 더 완전이 이해하고 난 뒤에 다시 자세한 풀이 과정을 기술하겠다...

---

문제 출처 : 백준 홈페이지