우선순위큐2 백준 21761 / C++ https://www.acmicpc.net/problem/21761 21761번: 초직사각형 1차원 공간에서의 선분, 2차원 공간에서의 직사각형, 3차원 공간에서의 직육면체를 생각해 보자. 선분의 크기는 변수 $A$로, 직사각형의 크기는 두 개의 변수 $A$와 $B$로, 직육면체의 크기는 세 개 www.acmicpc.net [ 풀이 ] 부피 ABCD에서 한 변을 증가시키면 (A+U)BCD가 된다. 그럼 매번 변화시키면서 1+U/A가 커지도록 해주면 된다. 그리디하게 매번 A,B,C,D중 제일 큰 U를 뽑아서 1+U/x가 제일 큰걸 매번 뽑아주면 된다. 기존 ABCD에서 이렇게 가장 큰 비율을 매번 곱해줘야 최대가 되는건 자명하다. 그 비율이 1보다 크기 때문에 항상 값이 커지기 때문이다. 매번 제일 큰 .. 2022. 8. 8. 백준 13975 / C++ https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net [ 풀이 ] 한번 합친 비용은 이후에 계속해서 더해진다. 즉, 처음에 작게 합칠수록 무조건 유리하다. 이제 작은것부터 2개씩 합쳐주면서 그걸 계속 더해나가면 된다. n제한이 1e6이므로 매번 작은걸 2개씩 골라주는건 우선순위큐로 찾아주면 O(logn)에 찾을 수 있다. 이제 구현만 해주면 된다. 최악의 경우 1e10이므로 long long을 써주자. [ 코드 ] #include using na.. 2022. 7. 21. 이전 1 다음