문제는 되게 쉬운 편이고, 시키는 대로 계산하기만 하면 되는데 Large의 경우에는 매우 숫자가 기하급수적으로 커지므로 pow함수를 이용하여 한번에 계산하기 보다는 그때그때 나머지를 연산하여 최대한 숫자를 줄이면서 계산해야 한다. 이 점만 유의하면 매우 쉬운 문제이다. 위의 내용을 바탕으로 코드를 구현하면 다음과 같다. #include #include #include #include #include #include using namespace std; typedef long long ll; int main(void){ int n; cin >> n; string data; cin >> data; int r = 31; int M = 1234567891; ll hash = 0; for(int i = 0; i ..

수학에서 학습한 공식을 활용하면 된다. nCr = n! / (n-r)!*r! 을 약분하면 r의 갯수만큼 n부터 1씩 작아지는 수들의 곱에서 r!을 나눈것으로 쉽게 구할 수 있다. 해당하는 알고리즘으로 코드를 작성하면 다음과 같다. #include #include #include #include #include using namespace std; int main(void){ int n, k; cin >> n >> k; int result_above = 1; for(int i = 0; i < k; i++){ result_above *= (n - i); } int result_down = 1; for(int i = 1; i < k + 1; i ++){ result_down *= i; } cout

방법론 자체는 11651번과 완전하게 동일하다. 다만, x가 증가하는 것이 먼저 고려되어야 한다는 것을 이용하여 compare함수만 수정해주면 된다. 해당하는 알고리즘을 활용하여 코드를 작성하면 다음과 같다. #include #include #include #include #include using namespace std; typedef struct{ int x; int y; }point; bool compare(const point value1, const point value2){ if (value1.x == value2.x){ return value1.y ..

이 문제는 x,y좌표를 제시하고 있으므로 x와 y를 저장하는 구조체를 만든뒤 sorting하면 된다. 단, 구조체를 정렬하는 방식에 대해서는 정의되어 있지 않으므로 따로 compare함수를 정의하여 처리해주어야 한다. 위의 내용을 활용하여 코드를 작성하면 다음과 같다. #include #include #include #include #include using namespace std; typedef struct{ int x; int y; }point; bool compare(const point value1, const point value2){ if (value1.y == value2.y){ return value1.x < value2.x; } else{ return value1.y < value2.y..

이 문제의 경우는 약간 독특하다. 일반적으로 오름차순으로 정렬하기 위해서는 가장 간단하게는 sort를 사용하면 되지만, 이 문제에서는 시간제한은 조금 널럴한 대신 메모리제한이 매우 제한적이다. 수가 10000으로 제한되어 있으므로 배열의 index와 숫자를 연결시켜서 저장시킨 뒤, 숫자가 들어오면 해당 배열의 값을 1 증가시키는 방식으로 메모리를 아낄 수 있음을 느끼고 문제를 접근했으면 된다. 위의 알고리즘으로 문제를 접근하면 다음과 같다. #include #include #include #include #include using namespace std; int main(void){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); in..

이 문제에서 가장 중요한 지점은, 입출력이 최대 200000 까지 되므로, 빠른 입출력을 활용하여 시간을 출여야 한다. 왜 그렇게 해야하는지에 대해서는 입출력 스트림 관련해서 상당히 복잡하므로, 실력을 키우기 전까지는 그냥 받아들이고 쓰는 것으로 하자. 방법은 다음과 같다. 메인함수에 해당 내용을 최상단에 쓰면 된다. ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 단, 이 방법을 쓰는 경우에는 getchar 같은 것들을 못쓴다는 점은 유의해야 한다. 추가적으로 이 문제의 경우에는, 존재하는지 아닌지만 판단해주면 되므로 정렬 후에 이분탐색으로 판단하는 것이 쉽다. 해당하는 알고리즘으로 코드를 구현하면 다음과 같다. #include #in..

이 문제를 요약하자면 1. 데이터를 받고 2. 자기보다 작은 숫자의 갯수를 출력한다. 라고 볼 수 있다. 즉, 이 문제를 풀기 위해서는 다음의 과정을 겪어야 한다. 1. 정렬을 한다. 2. 자기보다 작은 숫자의 갯수만 카운트 하되, 서로 다른 좌표의 갯수이므로 중복되는 것은 제거한다. 이때, 정렬하는 과정에서 O(nlogn)이고, erase까지 하는데 O(nlogn)가 사용된다. 추가로 자기보다 작은 숫자의 갯수를 전부 다 고려하려면 O(n^2)인데, 이 경우에는 시간 초과가 나므로 이분탐색을 활용해서 진행을 해주면 O(nlogn)이므로 충분히 2초안에 통과할 수 있음을 확인할 수 있다. 위의 방식을 활용하여 코드를 짜주면 다음과 같다. #include #include #include #include u..

가장 쉽게 생각할 수 있는 것은 브루트 포스이다.(전부 다 해보는 것) Brute force방법으로 하기 위해서는 숫자를 작은 것부터 계속해서 숫자를 키워나가면서 각 랜선을 해당 숫자로 나눈 몫의 합이 n보다 크거나 같으면 계속해서 숫자를 키워나가다가 n보다 작은 타이밍이 오면 그 직전까지의 숫자를 출력하는 방식으로 이해할 수 있다. 다만, 이 방식으로 진행하게 되면 시간초과가 나게 된다. 왜냐하면, 고려해야할 숫자의 범위가 maximum이 최대 랜선의 길이 x k(랜선의 숫자만큼 몫을 구해야하므로)가 된다. 이때 시간제한이 2초이므로 대략 10^8 * 2의 연산을 훨씬 초과한다. 즉, 단순히 연산하는 방식으로는 처리할 수 없음을 파악할 수 있다. 그 다음으로 생각할 수 있는 것은 이분탐색이다. 이분탐색..