[모각코 / 240202] 알고리즘 문제 풀이 (백준 - 그리디 부수기)

 

 

안녕하세요. 모각코 5일차입니다. 

 

 

오늘은 그리디 알고리즘을 복습하고 풀어보는 시간을 가졌습니다. 

 

 

그리디 알고리즘이란 근사 알고리즘으로 현 상황에서 할 수 있는 최선의 선택에만 집중하는 일입니다. 그러므로 현 상황에서 최적의 해가 전체의 최적의 해라는 보장이 없습니다.

 

전체의 해의 보장이 되기 위한 조건은 현재 선택이 미래의 선택에 영향을 주지 않아야 합니다. 

 

 

브론즈 문제

 

2720

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

2720번: 세탁소 사장 동혁

 

import sys

n = int(sys.stdin.readline())
li = [int(sys.stdin.readline()) for i in range(n)]

for i in range(n):
    c = [0, 0, 0, 0]
    while li[i] > 0:
        if li[i] - 25 >= 0:
            c[0] += 1
            li[i] -= 25
        elif li[i] - 10 >= 0:
            c[1] += 1
            li[i] -= 10
        elif li[i] - 5 >= 0:
            c[2] += 1
            li[i] -= 5
        elif li[i] - 1 >= 0:
            c[3] += 1
            li[i] -= 1
    for i in range(4):
        print(c[i], end=' ')
    print()

 

 

10162

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

10162번: 전자레인지

 

import sys

T = int(sys.stdin.readline())
li = [0, 0, 0]

while T > 0:
    if T - 300 >= 0:
        li[0] += 1
        T -= 300
    elif T - 60 >= 0:
        li[1] += 1
        T -= 60
    elif T - 10 >= 0:
        li[2] += 1
        T -= 10
    else:
        break

if T != 0:
    print(-1)
else:
    print(li[0], li[1], li[2])

 

5585

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

5585번: 거스름돈

 

import sys

money = int(sys.stdin.readline())
money = 1000- money

cnt = 0

while money > 0:
    if money - 500 >= 0:
        cnt += 1
        money -= 500
    elif money - 100 >= 0:
        cnt += 1
        money -= 100
    elif money - 50 >= 0:
        cnt += 1
        money -= 50
    elif money - 10 >= 0:
        cnt += 1
        money -= 10
    elif money - 5 >= 0:
        cnt += 1
        money -= 5
    elif money - 1 >= 0:
        cnt += 1
        money -= 1

print(cnt)

 

 

4796

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

4796번: 캠핑

 

import sys

L, P, V = -1, -1, -1
index = 1

while True:
    L, P, V = map(int, sys.stdin.readline().split())
    if L == 0 and P == 0 and V == 0:
        break
    print(f"Case {index}: {V // P * L + min(V % P, L)}")
    index += 1

 

2810

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

2810번: 컵홀더

 

import sys

n = int(sys.stdin.readline())
seat = sys.stdin.readline()

L = 0

for i in seat:
    if i == 'L':
        L += 1

print(min(n, (int(L / 2) + (n - L) + 1)))

 

 

 

실버 문제

 

 

2839

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

2839번: 설탕 배달

 

import sys

n = int(sys.stdin.readline())
cnt = 0

if n % 5 == 0:
    print(n // 5)
else: # 5의 배수가 될 때까지 3을 빼줌
    while n > 0:
        n -= 3
        cnt += 1
        if n % 5 == 0:
            cnt += n // 5
            n = 0
    if n != 0:
        print(-1)
    else:
        print(cnt)

 

11399

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

11399번: ATM

 

# 맨 처음 수는 뒤에 있는 모든 수에 더해야 할 값이다.
# 그러므로 오름차순 정렬을 하여 작은 수 일수록 앞에 둔다.

import sys

n = int(sys.stdin.readline())
line = list(map(int, sys.stdin.readline().split()))

line.sort()
time = 0

for i in range(len(line)):
    time += sum(line[0:i+1])

print(time)

 

11047

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

11047번: 동전 0

 

import sys

n, k = map(int, sys.stdin.readline().split())
value = [int(sys.stdin.readline()) for i in range(n)]
cnt = 0

index = len(value) - 1

while k != 0:
    if k - value[index] < 0:
        index -= 1
    else: # cnt += 1, k -= value[index] 를 하게 되면 시간초과가 난다.
        cnt += k // value[index]
        k %= value[index]

print(cnt)

 

1541

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

1541번: 잃어버린 괄호

 

이 문제는 혼자서 괄호가 한 개여야하는 줄 알고 삽질하다가 괄호가 한 개가 아닌 걸 알고 다시 생각한 문제입니다. 

- 뒤에 +가 나오면 괄호를 두어  더한 값을 마이너스로 만들 수 있습니다. 따라서 -로 split 한 결과에 +로 split 하여 값들을 더하고 가장 첫번째 숫자에서 뺍니다. 

 

import sys

minus_li = sys.stdin.readline().split('-')
num = []

for i in minus_li:
    sum = 0
    tmp = i.split('+')
    for j in tmp:
        sum += int(j)
    num.append(sum)

n = num[0]
for i in range(1, len(num)):
    n -= num[i]
print(n)

 

1931

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

1931번: 회의실 배정

 

회의실 배정 문제의 경우, 가장 일찍 끝나는 회의 순으로 정렬을 하고 시작 시간을 기준으로 한 번 더 정렬을 진행합니다. 

 

import sys

n = int(sys.stdin.readline())
li = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
end = 0
cnt = 0

li.sort(key=lambda x:(x[1], x[0]))

for newStart, newEnd in li:
    if end <= newStart:
        cnt += 1
        end = newEnd

print(cnt)