본문 바로가기

프로그래밍/백준 복기36

[DP] 백준 11726: 2*n 타일 https://www.acmicpc.net/problem/11726 타일을 맞춘다고 표현했지만 결국 문제에서 요구하는 것은 '1과 2를 나열하여 n을 맞추는 경우의 수' 일 것이다. 가로가 2인짜리 블럭을 사용하면 그 아래도 꼼짝없이 같은 블럭으로 채워야지, 다른 경우가 있을 수 없기 때문이다. 맨 처음에 재귀함수를 이용한 시도에서는 (예제의) 정답은 다 맞췄지만 시간 초과가 났다. 그래서 시간을 줄이기 위해 memoization을 사용하기로 했다. 먼저 n=1인 경우는 ㅣ 한 가지 경우의 수밖에 없고, n=2인 경우는 ㅡ 한 가지 경우의 수밖에 없다면,n=3인 경우 ㅣㅣㅣ,ㅣㅣㅡ, ㅣㅡㅣ,ㅡㅣㅣ 4 가지 수가,n=4인 경우, ㅣㅣㅣㅣ,ㅡㅡ,ㅣㅣㅡ,ㅣㅡㅣ,ㅢㅣ 5가지 수가 존재한다.  여기서 f(n) =.. 2024. 11. 17.
[이분탐색] BOJ 2512: 예산 https://www.acmicpc.net/problem/2512 예산 내에서 지자체가 요구한 예산들 다 커버할 수 있으면 지자체 중 요구한 예산이 가장 큰 지자체의 예산을, 그렇지 않으면 특정 상한선을 정해서 그 위로는 자르고, 전체 예산안을 만족할 수 있는 상한선 중 가장 큰 값을 반환하면 된다. 전자는 그냥 전체 요구 예산의 합이 예산 한도보다 낮으면 최대값을 반환하면 될 것이고, 후자 쪽이 binary search를 통해 상한선의 최대값을 찾아야 하는 문제이다. #include #include #include using namespace std;int answer;void findMaximum(vector &budget, int min, int max, int maxBudget){ if(mi.. 2024. 11. 6.
[Greedy] 백준 4796: 캠핑 https://www.acmicpc.net/problem/4796 예전에 설탕 문제 풀었던 것을 기억하자. https://gaebaldosamoodosa.tistory.com/79 연속된 P일 중 L일만 사용 가능하다는 것을 일종의 큰 상자로 생각하자. 요컨대 박스 무게는 P이고 안에 포장 빼고 실제 내용물이 L 들어 있는 것이다. 그리고 남는 여분은 작은 상자로 포장된다고 생각하자. 큰 상자를 고르는 것이 다른 상자의 선택에 영향을 미치지 않고, 매 순간 가능하다면 작은 상자 대신 큰 상자를 선택하는 것이 결국 가장 많은 내용물을 가져가는 결과를 도출할 것이다. 다시 말해 한 단계의 선택의 다음 단계의 선택에 영향을 미치지 않고, 매 순간 최적의 해가 문제 전체의 최적의 해가 될 것이기 때문에 Gree.. 2024. 10. 23.
[이분 탐색] 백준 2805: 나무 자르기 https://www.acmicpc.net/problem/2805 이분 탐색의 기본을 사용하는 문제이다. 먼저, 절단기 높이의 최소값은 0이고, 최대값은 나무들 중 가장 높은 나무의 높이이다. 따라서 초기에 min = 0, max = max(tree) 라고 하자. 우리가 구해야 할 것은 "원하는 만큼 나무를 가져갈 수 있는 절단기의 최대 높이" 이다. 따라서 절단기 높이에 따라 구할 수 있는 나무의 양이 요구치보다 적을 때는 절대 정답이 될 수 없되 절단기를 더 낮추어야 하므로, max = mid-1로 설정하고 다시 이분탐색을 진행한다. 반면 절단기 높이에 따라 구할 수 있는 나무의 양이 요구치보다 많을 때는 정답이 될 수 있되 절단기를 더 높여서도 해당하는 만큼의 나무를 구할 수 있는지 알아봐야 한다... 2024. 10. 22.

티스토리툴바