[C/C++] 백준 #1669 멍멍이 쓰다듬기(수학)
멍멍이 쓰다듬기 문제는 1부터 n까지의 합을 계산하는 것을 응용합니다. 첫째날과 마지막날은 1cm가 되어야 하고, 매일 조절할 수 있는 양이 1cm이므로, 10cm를 늘려야 한다면, 1cm, 2cm, 3cm, 2cm, 1cm, 1cm 형태가 되어야 합니다. 늘려야 하는 양이 y cm라고 했을 때, x는 최대값이 됩니다. 즉, 10cm를 늘려야 한다면, 1cm, 2cm, 2cm, 1cm 형태로 늘리는 형태입니다. 그러면 총 6cm 길이가 되고, 남은 길이는 4cm가 됩니다. 그러면 x+1만큼을 제하면, 1cm가 남습니다. 그러면 그 값은 이제까지 나왔던 값 중에 반드시 하나가 됩니다. 일단 다음과 같은 식을 이용해서 우리는 x값을 구합니다. \[ x^2 + x \le y \] \[ x \le \frac{-..
2022. 9. 25.
[C/C++] 백준 #1655 가운데를 말해요(힙)
이번 문제는 구간의 중간수 구하던 문제와 같이 두개의 힙을 이용해서 풀 수 있는 문제입니다. 왼쪽은 최대힙(max heap)을 오른쪽은 최소힙(min heap)을 운영합니다. 왼쪽 힙은 오른쪽 힙의 개수보다 1개 크거나 같아야 합니다. 1, 5, 2, 10, -99, 7, 5 순으로 숫자가 불리었고, 이번에 10이 불리는 차례였다면, 왼쪽의 최대힙은 [ 2, 1 ] 이 들어가 있고, 오른쪽 최소힙은 [5]가 들어가 있습니다. 10을 왼쪽힙의 최대값 2와 비교해서 작으면 왼쪽에, 크면 오른쪽에 넣습니다. 이 경우엔 2보다 큰 수이므로 오른쪽에 들어가 있게 됩니다. 그러면 [ 2, 1 ]과 [ 5, 10 ] 이 되고, 두 힙의 크기가 같으니, 힙간 원소 이동은 없습니다. 왼쪽힙의 가장 큰 값을 출력하면 2가..
2022. 9. 22.
