코테 연습 - 그리디 기초

11047 - 동전 0

그리디 기초, 매우 쉬운 문제
동전의 합으로 금액 맞추기
가장 큰 돈의 단위부터 나눠나간다 - local optimal

11047 동전 0 
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
lst = []
for _ in range(n):
    x = int(input())
    lst.append(x)

lst.reverse()
ans = 0
for i in range(n):
    if k == 0:
        break
    if k >= lst[i]:
        a = k // lst[i]  # 몫
        k = k % lst[i]  # 나머지로 갱신
        ans += a
print(ans)

---

1931번 - 회의실 배정

풀이를 봤나요? Y
아이디어 - 당장 해를 생각, 그 최적해로부터 발전
끝나는 시간으로 정렬
-> 시작지점을 기준으로 정렬, 종료 시간을 기준으로 정렬.

import sys
input = sys.stdin.readline

n = int(input())
lst = []
for _ in range(n):
    x, y = map(int, input().split())
    lst.append([x, y])

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

cnt = 1
end = lst[0][1]
for i in range(1, n):
    if lst[i][0] >= end:
        cnt += 1
        end = lst[i][1]
print(cnt)

---

11399 - ATM

덧셈의 합
3 1 4 3 2
3+
3+1+
3+1+4+
3+1+4+3+
3+1+4+3+2
= 결과합이 누적합, 순서에 따라 달라진다.
그리디
인출시간 순으로 정렬하면
가장 적은 값을 가장 많이 누적함
그리디 기초 - 쉬운문제

sum(arr[:i]) 생각했는데 안되서 이중 for문으로 품

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
rst = 0
# 누적합 구하기
for i in range(len(arr)):  # 5
    for j in range(0, i+1):
        rst += arr[j]
print(rst)

---

13305 - 주유소

주유비용 계산

예제
필요한 기름양 = sum(도로길이)
처음 도시에서 모두 주유 = 56 = 30원
분할 주유 = 52L + 23L + 41L = 20원
분할 주유2 = 52L + 24L = 18원

입력) 각 주유소 기름값, 도로 길이
출력) 최소 비용
도로 길이가 있어서 6L를 마음대로 분배 못함.
[2, 3, 1]

아이디어 -
그리디가...주유소에 도착한 순간에 가장 싼 주유소에서 가장 많이 주유하고 간다.
젤나가 맙소사 전혀 그리디하게 접근하지 못했다..

주유소와 조건에 집하다가 코딩 스타일에서 많이 벗어나버렸다.
뻘 풀이하는데 시간을 꽤 오래썼고
그리디한 방식으로 접근하지도 못했다.
발상을 전혀 하지 못했고 풀이는 잘 봤다고 생각한다.

import sys
input = sys.stdin.readline

n = int(input())
dist = list(map(int, input().split()))  # [2 3 1] N개
cost = list(map(int, input().split()))  # [5 2 4 1] N-1개

c = cost[0]
rst = 0
for i in range(n-1):
    if c > cost[i]:
        c = cost[i]
    rst += c*dist[i]
print(rst)

---

1541 - 잃어버린 괄호

55-50+40
괄호치기
'-' 나옴 : 다음 '-' 나올 때까지 파싱해서 더함
그래야 빼는 값이 최대가 됨

모르는 부분
5 5 - 5 0 + 4 0 - 2 0 + 3 0 - 10
입력 int형으로 분리

풀이봤냐? Y
'-'와 '-'사이를 다 더해서 빼준다
는 건 알겠는데 그 사이를 더하는 방법을 모르겠음

split('-') 사용하면 입력에서 - 단위로 끊어준다.
int 정수형을 사용하면 앞자리 불필요한 0이 삭제된다.
'-' 기준으로 자르면 처음 숫자 이후로 다 더해서 빼면 됨.

import sys
input = sys.stdin.readline

n = str(input())
m = n.split('-')

ans = 0

x = sum(map(int, m[0].split('+')))
if n[0] == '-':
    ans -= x
else:
    ans += x

for item in m[1:]:
    x = sum(map(int, item.split('+')))
    ans -= x

print(ans)

이해는되는데 왜 그리디인지는 모르겠다.