안녕하세요. 모각코 5일차입니다.
오늘은 그리디 알고리즘을 복습하고 풀어보는 시간을 가졌습니다.
그리디 알고리즘이란 근사 알고리즘으로 현 상황에서 할 수 있는 최선의 선택에만 집중하는 일입니다. 그러므로 현 상황에서 최적의 해가 전체의 최적의 해라는 보장이 없습니다.
전체의 해의 보장이 되기 위한 조건은 현재 선택이 미래의 선택에 영향을 주지 않아야 합니다.
브론즈 문제
2720
https://www.acmicpc.net/problem/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
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
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
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
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
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
# 맨 처음 수는 뒤에 있는 모든 수에 더해야 할 값이다.
# 그러므로 오름차순 정렬을 하여 작은 수 일수록 앞에 둔다.
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
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
이 문제는 혼자서 괄호가 한 개여야하는 줄 알고 삽질하다가 괄호가 한 개가 아닌 걸 알고 다시 생각한 문제입니다.
- 뒤에 +가 나오면 괄호를 두어 더한 값을 마이너스로 만들 수 있습니다. 따라서 -로 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
회의실 배정 문제의 경우, 가장 일찍 끝나는 회의 순으로 정렬을 하고 시작 시간을 기준으로 한 번 더 정렬을 진행합니다.
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)
'2024 겨울 모각코 - 내 장점은 algorithm' 카테고리의 다른 글
[모각코 / 240209] 알고리즘 문제 풀이 (백준 - 그리디 부수기) (2) | 2024.02.13 |
---|---|
[모각코 / 240126] 알고리즘 문제 풀이 (프로그래머스 - bfs) (1) | 2024.01.30 |
[모각코 / 240119] 알고리즘 문제 풀이 (프로그래머스 - 스택/큐) (1) | 2024.01.22 |
[모각코 / 240112] 알고리즘 문제 풀이 (코드트리 - 백트래킹) (0) | 2024.01.17 |
[모각코 / 240105] 알고리즘 문제 풀이 (코드트리 - 시뮬레이션) (1) | 2024.01.11 |