[백준] 11047, 1931, 2217 (파이썬)

이코테 교재의 순서에 맞춰서 진도를 나가고 백준에서 관련 문제를 풀어보는 식으로 공부해나갈 예정이다. 오늘 학습한 내용은 그리디. 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 이 알고리즘은 알고리즘 공부에서 가장 먼저 해야하는 개념이라고한다. 직접 문제를 풀어보면서 그 이유를 느꼈다. 시작하는 입장에서 가장 생각하기 쉬운 방법임과 동시에 생각하는 습관을 들이기 좋은 것 같다. 관련 문제를 한동안 풀어보도록 하겠다.

백준 11047번 동전 0

import sys
N,K = map(int,(sys.stdin.readline().split()))
A = list()
count = 0
for i in range(N):
    A.append(int(sys.stdin.readline()))
A.reverse()
for j in range(len(A)):
    if K//A[j]>0:
        count += K//A[j]
        K = K-(A[j]*(K//A[j]))
    elif K==0:
        break
print(count)

백준 1931번 회의실 배정

import sys
N = int(sys.stdin.readline())
Time = list()
for _ in range(N):
    Time.append(list(map(int,(sys.stdin.readline().split()))))
Time = sorted(Time, key=lambda x: x[0]) # 시작하는 시간 기준 오름차순 
Time = sorted(Time, key=lambda x: x[1]) # 끝나는 시간 기준 오름차순
Time_locate=0
count=0
for i,j in Time:
    if i >= Time_locate:
        count+=1
        Time_locate=j
print(count)

백준 2217번 로프

import sys
N = int(sys.stdin.readline())
rope = list()
for _ in range(N):
    rope.append(int(sys.stdin.readline()))
rope.sort()
n_count = N
rope_list = list()
for i in range(N):
    rope_list.append(n_count*rope[i])
    n_count -= 1
print(max(rope_list))