greedy 썸네일형 리스트형 BOJ 29202 - 책가방 (D5) 2023 KSA Automata G번이다. 아레나 당시에 27점까지 긁었는데, 27점 풀이로 44점까지 긁을 수 있었다는 걸 대회 때 알았으면 더 좋았을 것 같다. 사용 알고리즘 Segment Tree + 좌표 압축 && 그리디 (우선순위 큐) 풀이 일단 섭태3을 풀어보자. 부피의 최댓값만 고려하면 되므로 부피 기준으로 오름차순으로 정렬하고 정렬된 배열에서 x번 책을 고르면, 1~x-1 사이 책은 모두 부피가 \( V_{x} \) 이하이다. 따라서 이 중에서 무게가 작은 k-1개를 골라주는게 이득이다. 이는 우선순위 큐(max heap)의 크기를 k-1으로 유지하고, 하나의 변수를 관리하는 것으로 해결할 수 있다. for(int i = 0 ; i < n ; i++)v[i].i=i+1; sort(all(v.. 더보기 BOJ 1201 - NMK (P3) 사용 알고리즘 Greedy-Style Constructive 풀이 BOJ 27244의 확장판이다. https://sehujeong.tistory.com/20에서 설명한 그룹을 확장해보자. 그룹의 크기가 최대 K이고, 그 개수가 M개면 똑같이 풀 수 있을 것이다. 따라서 N을 K+a1+a2+...+a_M-1 꼴로 나타낼 수 있으면 27244와 똑같다.(1k; if(!(m+k-1 더보기 BOJ 27244 - Монотонная подпоследовательность (G1) 사용 알고리즘 Greedy-Style Constructive 풀이 문제를 아주 짧게 요약하면 다음과 같다. N, K (k; if(k*k 더보기 BOJ 2613 - 숫자구슬 (G2) 알고리즘 분류 Dynamic Programming Greedy Binary Search Parametric Search 풀이 풀이 1: Greedy, O(N^3) N이 최대 300이므로 O(N^3)까지 고려할 수 있다. 따라서 임의의 구간 [l, r]을 골라서, [l,r]의 합이 최댓값이 되게 할 수 있는지를 빠르게 구할 수 있으면 된다. [l,r]의 합을 x라 하자. 배열의 처음부터 시작해서 값을 연속해서 더해나간다. 이 때, 합이 x 초과일 경우 새로 그룹을 갱신한다. (단, 하나의 값이 x 초과일경우는 불가능하다.) [l,r]에 대해서는 예외처리를 해준다. 위 알고리즘은 x가 최댓값이 되게 하면서 그룹의 크기를 최소화하는 그리디적인 방법이다. 만약 위 알고리즘대로 만든 그룹의 개수가 m보다 크다면,.. 더보기 골드 그리디 랜덤 (2) 오늘도 열심히 그리디를 하자. 1. BOJ 2759 - 팬케이크 뒤집기 (G4) http://boj.kr/2759 2759번: 팬케이크 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 숫자 여러개가 공백으로 구분되어있다. 첫 번째 숫자는 팬케이크의 개수 N이고, 그 다음 N개의 숫자는 팬케이크의 크기이다. www.acmicpc.net sol) constructive(그리디 스타일) 자명하게도 n번 팬케이크가 n번 위치에 있지 않으면 반드시 n번 팬케이크를 1번으로 옮긴 후, n번으로 옮겨야 한다. 이렇게 옮기고 나면 n-1번 팬케이크가 n-1번 위치에 있는지 판별하는 문제로 바뀐다. 위 과정을 계속 반복하면 된다. 이때 1번 위치에서는 뒤집어도 상태가 똑같으므로 굳이 뒤집을 필.. 더보기 골드 그리디 랜덤 (1) 그리디 연습이 좀 필요하다고 느껴서 랜덤으로 그리디 문제를 풀어봤다. 1. BOJ 20311 : 화학 실험 (G5) http://boj.kr/20311 20311번: 화학 실험 화학 실험을 하던 윤이는 일렬로 나열해 놓은 $N$개의 시험관에서 재밌는 특징을 발견했다. 그 특징은 모든 이웃한 시험관 쌍에 대해, 두 시험관에 들어 있는 시약의 색깔이 서로 다르다는 점이 www.acmicpc.net solve) 그리디(sort) + constructive 꽤나 직관적인 그리디 문제이다. 색깔 수가 많은 숫자부터 배치하는데, 앞쪽부터 1칸씩 띄워서 배치하면 된다. 이때 배치하다가 갯수가 부족하면 다음 색깔부터 이어서 배치하되, 다른 색깔은 인접해도 무방하므로 다음과 같이 배치한다. 예를 들어 1번 색과 2번 색.. 더보기 이전 1 다음
