반응형 컴퓨터 사이언스65 Codeforces #582 (div 3) 후기 http://codeforces.com/contest/1213 작성일 : 190830 div3이라 쉬웠는데도 D번에서 아예 논리를 잘못 생각해서 말려버려서 좋은 결과는 내지 못했다. A. Chips moving 결국에는 짝수번 움직일 때는 공짜고 홀수번 움직일 때는 1의 요금이 있으므로 전체 숫자 중 짝수와 홀수의 개수 중 min을 택하면 된다. B. Bad prices 자기보다 더 싼 가격이 뒤에 있으면 bad price라는데 주어진 배열을 (index, price)로 저장한 후 price를 이용하여 정렬한 후에 앞에 indx보다 더 작은 값이 뒤에 가있으면 그거만큼 count해준다. C. Book Reading 진짜로 1~n까지 m으로 나눠지는 것들의 digit을 일일이 구하면 망하는 문제. 힌트는 .. 2019. 10. 8. [c++] 백준 #17399 트리의 외심 (190826) 직관대로 풀면 되는 문제. 단 case 처리 시 조금 까다로운 면이 있다. 외심 후보 3개를 두 점의 중점으로 고르고 나머지 한 점에서의 거리와 두 점에서의 거리가 같은 지 비교하면 끝. 만약 3개의 점 중 2개의 점이 동일한 경우에는 한번만 get_center해주면 됨. 3개의 점이 다 동일한 경우에는 그냥 그 점을 출력. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define swap(a,b){int t=a; a=b; b=t;} #define N_MAX 100010 int N, Q; vector graph[N_MAX].. 2019. 10. 8. [c++] 백준 #17398 통신망 분할 (190826) 연결된 애를 쪼개는 것에 대해 물어보는 문제였는데, 반대로 쪼개져 있는 애들을 합치는 방식으로 disjoint set으로 구현한다.(신기..) 그래프를 union할 때마다 각 set의 원소의 개수를 서로 곱해서 cost를 더해준 다음에 빼주면 됨. 이때 원소의 개수를 어떻게 count할 지가 고민이었는데 모두 다 1로 초기화한 다음에 union할 때마다 부모(대빵) 노드 기준으로만 자기 밑에 원소 몇 개 있는 지 더해주면 된다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define N_MAX 100010 int p[N_.. 2019. 10. 8. [c++] 백준 #1987 알파벳 (190823) 완전탐색 문제. bfs 식으로 하면서 하면 되겠지? 하고? 코드를 짰는데 메모리 초과가 나왔다. 비트마스크도 써서 메모리 초과가 날 이유가 없는데 질문검색란에 나처럼 bfs식으로 푼 사람의 질문에 대한 답변을 보니 queue가 문제라고 한다. 뭔가 막연히 queue가 커지면 뻑가서 안된다는데 구체적으로 상상이 잘 안가서 직접 써봤다. (https://www.acmicpc.net/board/view/40634 에서 가져온 반례이다.) in: 20 20 ABCDEFGHIJKLMNOPQRST BCDEFGHIJKLMNOPQRSTU CDEFGHIJKLMNOPQRSTUV DEFGHIJKLMNOPQRSTUVW EFGHIJKLMNOPQRSTUVWX FGHIJKLMNOPQRSTUVWXY GHIJKLMNOPQ.. 2019. 10. 8. 이전 1 ··· 8 9 10 11 12 13 14 ··· 17 다음 반응형