그리디11 백준 25315 / C++ https://www.acmicpc.net/problem/25315 25315번: N수매화검법 화산파의 장로 우경은 새로운 무공 N수매화검법을 창안했다. N수매화검법은 이십사수매화검법을 발전시킨 검법으로 총 $N$개의 베기(검으로 무언가를 베는 동작)로 이루어진다. N수매화검법은 2 www.acmicpc.net [ 풀이 ] 선분교차여부는 CCW로 잘 구해주면 된다. 이제 (m+1)*w[i] 이 부분을 처리해야 한다. 서로 교차하는 것끼리 묶었다고 해보자. 묶은 것들은 m이 최대부터 시작하게 된다. (안벤 베기의 개수니까) 벤 후엔 계속 m은 감소하므로 따라서 묶은것들은 가중치가 작은것부터 처리해야 값이 최소가 된다. (그리디하게 최소는 최대와, 최대는 최소와 만나야 곱들의 합이 최소가 됨) 이제 구현해보.. 2022. 8. 8. 백준 14908 / C++ https://www.acmicpc.net/problem/14908 14908번: 구두 수선공 최소 보상금을 지불하는 작업 순서를 출력해야 한다. 모든 작업은 입력에서의 번호(1~N)로 표시해야 한다. 모든 정수는 한 줄로 표시해야 하며, 각 작업은 공백 문자로 구분한다. 여러 가지 해답 www.acmicpc.net [ 풀이 ] (T1 S1) (T2 S2) ... (Tn Sn) 이 최적해라고 가정하자. 이제 (T1 S1) (T2 S2)를 교환했을 때 값을 구해서 비교하자. 양식의 차를 비교하면 1식-2식 = T1S2-T2S1이 되고 최적해조건에 따라 T1S2 < T2S1을 만족해야 한다. 즉, T1/S1 < T2/S2 이다. 중간에 있는 (Ti Si)와 (Ti+1, Si+1)을 교환했을 때도 다 소거되고.. 2022. 8. 5. 백준 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 2 3 다음