알고리즘 문제 | 떡볶이 떡 만들기
비슷한 백준 문제 https://www.acmicpc.net/problem/2805
문제에서 요구하는 것은 위 백준 문제와 똑같다. 단순히 떡볶이에서 나무로 바뀐것이다.
접근
1차
일단 문제를 보고 이진 탐색을 통해서 최대로 자를 수 있는 길이를 찾아야겠다고 생각했다. 그래서 떡볶이 길이 배열을 이진 탐색을 통해서 중간점을 찾는 방식으로 구현하였지만 생각해보니까 배열에 없는 숫자가 답일 수 있다. 따라서 이 접근은 틀렸다는 것을 깨달았다.
2차
이진 탐색을 통해서 최대 최소 값을 건내주고 그 둘의 평균을 mid 로 하여 target 과 같은지 탐색하는 방법으로 구현했다. 그러긴 위해서 mid 를 건내주면 나머지 떡의 길이의 합을 구하는 함수를 따로 구현했는데 이 함수의 복잡도가 O(N) 이고 이진 탐색이 O(logN) 으로 어느정도 괜찮겠다 싶었다.
def sum_left(array, length):
result = 0
for i in array:
left = i - length
if left <= 0:
continue
result += left
return result
def binary_search(array, target, min, max):
while min <= max:
mid = (min + max) // 2
tmp = sum_left(array, mid)
if tmp == target:
return mid
elif tmp > target:
max = mid - 1
else:
min = mid + 1
return -1
그러나 이 코드도 어딘가 문제가 있었다.. 이틀동안 고민하고 풀어봤는데 시간만 있으면 풀 수 있을 것 같으나 더이상 시간을 소비할 수 없어서 일단 답을 보고 배우자는 생각을 하게 되었다.
해설
전체적인 흐름은 내가 시도 했던 방법과 비슷했다. 하지만 위의 코드와 해설과 다른 부분은 바로 조건 부분이였다. 나는 위 코드에서 tmp 가 target 과 같아지는 경우와 아닌 경우를 나눠야 하고 그에 대한 처리를 따로 해줘야 하는게 이부분에서 계속 뭔가 잘 안풀렸다. 그런데 해설을 보니까 그냥 단순히 tmp < m 인 경우에는 max = mid - 1 로 해주고 아닌 경우에는 일단 답이 될 수 있으니까 result 라는 변수에 mid 를 저장해두고 start = mid + 1 로 해주어 다시 반복문을 도는 방식이였다. 이렇게 구현하면 다시 조건에 충족 되는 경우에는 result 가 업데이트 되고 업데이트 되는 result 는 기존에 result 의 값보다는 큰 값이 들어오게 된다.
import sys
def solution():
n , m = list(map(int, input().split()))
array = list(map(int, sys.stdin.readline().rstrip().split()))
start = 0
end = max(array)
result = 0
while start <= end:
mid = (start + end) // 2
total = 0
for i in array:
if i > mid:
total += i - mid
if total < m: # 떡이 부족한 경우
end = mid - 1
else:
result = mid
start = mid + 1
print(result)
solution()
참고로 이렇게 solution 이라고 따로 함수를 만들어서 실행시키는 방식으로 하면 함수 없이 그냥 코드를 작성하는 것보다 더 빠르게 처리가 된다. 그 이유는 만약에 함수안에 구현을 해두면 변수들이 local 변수로 선언되는 반면 함수 없이 구현하면 global 로 선언되는 것이기 때문에 유의미한 속도 차이가 발생한다고 한다. (출처 : https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function)
Author And Source
이 문제에 관하여(알고리즘 문제 | 떡볶이 떡 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jhon3242/알고리즘-문제-떡볶이-떡-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)