애드혹2 [백준] 17036 - Sleepy cow Herding (c++) https://www.acmicpc.net/problem/17036 문제 요약1차원 들판에 N마리의 소 위치가 주어진다. 소를 연속된 위치에 모아야 한다(1,2,3,4 같이). 양 끝에 있는 소중 하나를 선택해서 그 소를 제외한 소들의 양 끝 위치 사이에 소가 없는 위치로 이동시킬 수 있다. 목표를 만족하는 이동횟수의 최솟값과 최댓값을 구해라. 풀이 (NlogN)애드혹n-연속된 좌표 n개에 최대 소 개수가 최솟값이 된다. 하나씩 끼워 넣는다 생각하면 된다. 예외가 딱 하나 있는데 1,2,3,4,7 이런식으로 하나만 2칸이상 떨어져 있으면 1이 아니고 2다. 최대는 양끝 중 하나를 두개 이상 연속하게 만들어 빈칸을 다 방문하는 것이다. #include using namespace std;int main().. 2025. 1. 14. [백준] 29200 - 문제 수 줄이기 (c++) https://www.acmicpc.net/problem/29200 문제 요약N크기의 수열이 주어진다. 수열을 구간으로 분할하는데 인접한 수열끼리 크기가 같으면 안 된다. 수열끼리 xor한 값의 합이 최대가 되도록 분할하고 합을 출력해라. 풀이 (N)DP애드혹일단 xor은 각 비트 자리에 1이 단 하나만 있어야 비트가 켜지기 때문에 잘게 쪼갤 수록 이득이란 걸 알 수 있다. 언뜻 보고 1,2,3 크기로만 분할해서 최댓값을 만들 수 있을 줄 알았지만6 1 1 2 4 8 8이런 반례 케이스가 있었다(3까지 포함하면 22, 4까지 포함하면 24 나옴). 4까지 포함하니 최댓값을 만들 수 있었다. 제한시간이 넉넉해서 한 1~10까지 써도 상관은 없다. 제한적인 숫자로 최댓값을 구성할 수 있다는 걸 직감을 통해 .. 2024. 8. 28. 이전 1 다음