반응형 컴퓨터 사이언스/BOJ42 [c++] 백준 #3176 LCA : 도로 네트워크 (190828) 자신의 i번째 부모를 저장하는 배열을 응용한 문제. 결국 I번째 부모까지 연결한 간선 중에 제일 minimum한 거, 제일 maximum한 거를 배열로 저장한 후 나중에 lca 구하고 d~lca까지 갈 때 minimum, maximum edge 계산, e~lca까지 갈 때 minimum, maximum edge를 계산하는 방식이다. 예전에 어려워서 못풀었는데 풀게 되어서 기쁘다. #include #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_.. 2019. 10. 8. [c++] 백준 #2904 수학은 너무 쉬워 (190830) 주어진 연산을 너무 복잡하게 생각하지 말고 그냥 다 곱해버린다고 생각하면 편하다. 결국에는 특정한 소인수를 어느쪽에 넘겨서 최대공약수를 만드는데 전체 숫자의 곱은 일정하므로, 전체 숫자를 소인수 분해하면 이런 식으로 값이 나오니까 gca값을 구하면 된다. 변환 숫자의 경우에는 각각의 숫자에 대해서 이런 식이고 이런 식이라면 a #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define NUM 1000010 int A[101]; int soinsu[10.. 2019. 10. 8. [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. [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. 이전 1 ··· 4 5 6 7 8 9 10 11 다음 반응형