반응형 2019/1031 [c++] 백준 #11585 속타는 저녁메뉴 (190830) KMP 문제임을 바로 이해할 수 있었고, 원형으로 계산하기 위해 기존 string을 2번 붙여줘야함을 이해했다. 문제의 출력 방식이 귀찮다. 기약분수로 나타내기 위해서 KMP 위치와 전체 N길이 사이의 최대공약수를 구해서 나눠준다. 단, 틀렸습니다 처리를 하기 위해서는 2번 붙여준 기존 string 중 맨 마지막 글자는 빼고 KMP에 넣어줘야 문제가 발생하지 않는다. 왜냐하면, H == N인 경우 count할 때 문제가 생길 수 있기 때문이다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; int get_gca(int a, i.. 2019. 10. 8. 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. 이전 1 ··· 3 4 5 6 7 8 다음 반응형