문제를 보고 러프하게 풀이방법을 생각해보면 브루트포스가 있다.하지만, O(n^2)이라 시간초과가 날 것이다. 그러면 O(n) 혹은 O(nlogn) 정도의 로직으로 코드를 구성해야 한다. 최대 a개 만큼 반값할인을 받을 수 있다고 문제에 나와 있다.10개 중에 최대 3개를 할인받을 수 있다고 가정해보면해당 10개를 모두 구매할 수 있든 없든 항상 상위 3개를 할인받는 것이 가장 유리하다. 따라서 우리는 하위 a개를 고려할 필요없이 상위 a개의 반값할인만을 고려하면 된다.  이 문제를 풀기 위해서 우리는 매번 임의의 개수의 선물의 가격의 합을 구해야한다.이 작업만 해도 O(n)이기 때문에 누적합을 이용해서 이를 선처리해줄 것이다. 위의 굵은 글씨에 해당하는 두가지를 사용하려면선물들의 가격순으로 오름차순 정렬..

문제에 주어진 조건대로 구현하면 그리 어렵지 않게 해결할 수 있는 문제였다. p와 m이 300으로 매우 작고, 최대 방의 개수 또한 300개이므로 시간복잡도를 딱히 고려하지 않아도 된다. 정답 코드#include #include #include using namespace std;int p, m;pair player[300];vector> room[300];bool cmp(pair a, pair b){ return a.second > p >> m; for (int i = 0; i > player[i].first >> player[i].second; for (int i = 0; i cur_player = player[i]; for (int j = 0; j 0 && playe..

문제를 보고 가장 먼저 떠오른 생각은 그냥 브루트포스로 모든 경우를 확인하는 방법이었다.그러면 시간복잡도는 O(nm)이 되므로 시간 제한을 초과할 수 밖에 없다. 이때는 간단하게 이분탐색을 사용하면 된다.대신 칭호에 대한 상한전투력을 기준으로 이분탐색을 진행하면 안된다.칭호에 대한 상한전투력은 연속된 수가 아니고, 구간이므로 정확한 구간을 판단할 수 없다.따라서 칭호에 대한 인덱스를 기준으로 이분탐색을 수행해야 한다. 정답 코드#include using namespace std;int n, m, score;pair title[100000];int main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); cin ..

어떻게 해야 사전순으로 가장 빠른 문자열을 만들 수 있을까?'0'과 '1' 중 사전순으로 더 빠른 것은 '0'이다."10"과 "01" 중 사전순으로 더 빠른 것은 "01"이다.즉, 사전순으로 더 빠른 문자가 앞쪽에 올수록 사전순으로 빠른 문자열이 된다. 우리는 '0'이 최대한 앞에 나오고, '1'이 최대한 뒤에 나오는 문자열이 되도록 해야 한다.그러면 '0'은 뒤에서 부터 없애고, '1'은 앞에서 부터 없애면 된다. 이를 구현하는 것은 그리 어렵지 않다. 정답 코드#include using namespace std;string s, answer;int cnt0, cnt1;int main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_std..

문제에서 주어지는 정보의 종류가 많기 때문에이들을 잘 파싱하여 적절한 데이터로 가공하는 것이 중요하다. 우리에게 필요한 데이터는각 팀별 최종점수, 제출횟수, 마지막제출시간이다. 최종점수는 문제별 최종점수의 합산이고,제출횟수와 마지막제출시간은 로그를 파싱하면서 바로 구할 수 있다.문제별 최종점수의 경우 로그를 파싱하면서 업데이트하여 구할 수 있다. 이렇게 구한 3가지 데이터를 가지고, 랭크를 매기면 된다.랭크를 문제에서 주어진 조건대로 구현하면 쉽게 도출해낼 수 있다. 정답 코드#include #include using namespace std;int T, n, k, t, m;int main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_s..

오랜만에 화가 살짝(?) 나려고 하는 문제였다.자꾸 맞왜틀? 이 문제를 풀 때는 두 문자열의 다른 문자의 개수가 아닌두 문자열의 같은 문자의 개수에 집중해야 한다. 만일 다른 문자의 개수에 집중한다면 같은 문자는 몇개가 다른지특정 문자는 어느 문자열에서 더 많이 나타나는지 등을 고려해야 한다. 같은 문자의 개수에 집중한다면 간단하게 풀 수 있다.우선 두 문자열의 길이를 기준으로 바라보자.두 문자열의 길이가 같다면 비슷할 수 있고, 길이 차이가 1이어도 비슷할 수 있다.다만 길이 차이가 2이상이라면 어떤 수를 써도 비슷해질 수 없다. 길이가 같을 경우 같은 문자의 개수가 첫번째 문자열의 개수와 같거나 그보다 하나 작으면 비슷해질 수 있다. 길이가 1차이나는 경우는 첫번째 문자열의 길이가 더 긴지 짧은지에 ..