반응형 2019/1031 [c++] 백준 #2457 공주님의 정원 (190927) Greedy 방법. 회의실 배정과 비슷하게 풀면 된다. 3월 1일부터 11월 30일까지 매일 꽃이 하루에 한 개 이상 펴 있도록 꽃들을 선택할 때 선택한 꽃의 최소 개수를 출력해야 한다. 최소의 꽃을 선택하려면, 시작 시점이 증가하는 순서대로 정렬하고, 시작시점이 같으면 끝 지점이 작은 걸 위에 올린다. 정렬된 결과 예시는 다음과 같다. 1 1 5 31 1 1 6 30 5 15 8 31 6 10 12 10 시작 시간이 31(3월 1일)~1130(11월 30일)까지 갈 수 있다. 맨 처음에 끝 시간은 31로 초기화를 한다. 시작 시간이 제일 작은 애들부터 업데이트했기 때문에 맨 처음 애의 시작시간이 31보다 커버리면 아예 불가능하기 때문. 시작 시간이 현재 끝 시간보다 작은 애들을 탐색해보고,.. 2019. 10. 8. [c++] 백준 #14257 XOR 방정식 (190927) A+B = S, A^B = X를 만들 수 있는 (A, B) 쌍의 개수를 구하는 문제이다. 문제를 풀 때 집중해야 하는 것은 xor의 성질. xor 했을1이 되는 bit는 A나 B 둘 중 하나가 가지고 있을 것이다. 일단은 xor해서 0되는 bit는 A, B 둘 다 가지고 있지 않다고 가정하고 나머지 bit를 0으로 두자. 그러면 A^B = X가 되는 A, B의 경우의 수는 2^(켜진 비트 수) 만큼 된다. 이때 xor해서 0이 되는 경우는 모두 0으로 뒀으니 A, B는 모두 X의 각 비트를 나눠 가진 셈이니까 A + B = X이다. 그러면 이제 두 숫자 모두 켜져 있지 않은 비트를 하나씩 켜보면서 A + B = S를 만들 수 있으면(이 경우는 유일하게 하나 나온다) 가능한 모든 경우는 2^(.. 2019. 10. 8. [c++] 백준 #14458 소가 길을 건너 간 이유 10 교차점을 세는 방식이 생각하기 어려운 문제였다. 회전 시 생기는 교차의 수를 매번 새로 세줘야 하는데 naive 하게 구현하면 당연히 O(N^3)이라 시간 초과. 한 번 회전할 때마다 나름의 규칙성을 찾아보면, 회전 시 교차점의 수는 이전 교차의 수 – 현재 간선으로 생긴 교차의 수 + 새로 생기는 교차의 수가 된다. 이전 교차의 수는 회전할 노드보다 right가 더 큰 노드의 개수 (코드에서 N-right_idx[left_rev[i]) 새로 생기는 교차의 수는 회전할 노드보다 right가 작은 노드의 개수. (코드에서 right_idx[left_rev[i]) 이렇게 대략적으로 회전 시 교차선 수 개수 변화를 구할 수가 있는데, 관건은 맨 처음 상태에서 교차점 개수를 계산하는 것이다. 여기에.. 2019. 10. 8. 이전 1 ··· 5 6 7 8 다음 반응형