문제 링크
문제 요약
Lesson 16의 Greedy algorithms 에 해당한다.주어진 배열 A에는 밧줄의 길이들이 나열되어있고 K는 우리가 밧줄을 묶어서 만들어야하는 최소한의 길이라고 이해하자.
우리는 인접한 밧줄들끼리만 묶을 수 있고 묶은 밧줄의 길이가 K보다 크거나 같으면 된다. 이때, 우리가 K보다 크거나 같은 밧줄 개수의 최대값을 구해보자.
더 자세한 내용들은 위의 링크로 이동하여 확인해보길 바란다.
문제 풀이- 시간 복잡도 O(n)
def solution(K, A):
sum = 0
count = 0
for i in range(0, len(A)):
sum += A[i]
if sum >= K :
count +=1
sum =0
#print(count)
return count📌 고려해야할 점
- 어차피 인접한 밧줄들끼리만 묶을 수 있다.
- for문을 돌면서 각각의 밧줄을 순서대로 합하다가 K의 값보다 크거나 같아지면 count의 개수를 증가시키고 sum은 0으로 다시 초기화한다.
🙄 느낀 점
간단하게 stack을 이용하면 되는 문제이다.
