꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/9576 이분매칭으로 푼 사람들이 더 많지만 저는 그리디하게 접근해서 풀었습니다.b를 기준으로 오름차순 정렬을 한 상태에서 책을 나눠주면 풀리는 문제였습니다.그리디 문제들은 사실 그리디하게 풀 수 있는 근거가 있어야하지만 왜 이렇게 풀어야하는지는 증명하지 못하겠습니다.혹시 이렇게 풀어도 되는 이유를 아신다면 댓글 남겨주신다면 정말 감사하겠습니다. #include #include #include #include using namespace std; const int MAX = 1000 + 1; bool visited[MAX]; bool cmp(pair a, pair b) { if (!(a.second == b.second)) ret..

문제 링크입니다: https://www.acmicpc.net/problem/2831 N이 최대 100,000이기 때문에 O(NlogN)으로 풀어야하는 문제였습니다.저는 우선순위 큐를 이용해 풀었습니다. 알고리즘은 아래와 같습니다.1. 음수로 주어진 남성과 양수로 주어진 남성, 음수로 주어진 여성과 양수로 주어진 여성을 각각 다른 최소 우선순위 큐에 넣었습니다.2. 1번을 완료하고 음수로 주어진 남성과 양수로 주어진 여성을 그리고 양수로 주어진 남성과 음수로 주어진 여성을 짝을 맺게 했습니다.3. 2번의 전자 같은 경우 현재 남성과 짝을 맺을 수 있을 때까지 여성만 pop을 했고 짝이 맺어지면 그제서야 남성도 pop을 했습니다.(그리디하게 접근)4. 2번의 후자 같은 경우 현재 여성과 짝을 맺을 수 있을 ..

문제 링크입니다: https://www.acmicpc.net/problem/2828 쉬운 그리디 문제였습니다.바구니의 범위 내에 사과가 있는지 확인하고 없으면 왼쪽으로 움직일지 오른쪽으로 움직일지 판별하면 되는 문제였습니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; int J; cin >> J; int idx = 1; int result = 0; for (int i = 0; i > num; while (1) { bool flag = false; //범위 내에 사과가 있는지 확인 for(int j=i..

문제 링크입니다: https://www.acmicpc.net/problem/5585 그리디 알고리즘을 적용하여 푸는 문제였습니다.동전 배열을 내림차순으로 정렬하고 각 동전을 최대한 많이 사용하면 풀 수 있는 문제였습니다. #include using namespace std; int pay; int coin[] = { 500, 100, 50, 10, 5, 1 }; int minCoin(void) { int total = 1000 - pay; int cnt = 0; //greey하게 접근 for(int i=0; i= 0) { total -= coin[i]; cnt++; if (total == 0) //잔돈을 모두 반환했을 경우 반복문 탈출 break; } return cnt; } int main(void) ..

문제 링크입니다: https://www.acmicpc.net/problem/1783 아래와 같이 4가지의 경우로 나누어서 생각하면 됩니다.1. 세로가 1일 경우 움직이지 못하므로 1칸(시작하는 칸도 센다고 문제에서 명시)2. 세로가 2일 경우 2번과 3번의 조건을 최대 3번까지 이용 가능3. 세로가 3 이상일 경우i) 가로가 6 이하이면 1번과 4번 그리고 2번 혹은 3번 사용해서 최대 4칸ii) 가로가 7 이상이면 2번과 3번을 한번씩 사용하고 나머지는 1번과 4번 핵심은, 4회 이상 움직일 때 조건 1번~4번을 적어도 한번씩은 사용해야한다는 것이였습니다! #include #include using namespace std; int N, M; int main(void) { cin >> N >> M; i..

문제 링크입니다: https://www.acmicpc.net/problem/11509 처음에 Brute Force 방식으로 풀었기 때문에 TLE가 발생했습니다. 사실 O(N^2)이기 때문에 시간 안에 풀 수 있을 줄 알았지만 문제에서 요구하는 시간 복잡도는 O(N)이였습니다.이 문제의 핵심은 더 높은 곳에서 날아오는 화살의 존재 여부를 판단하는 것이였습니다. #include #include //memset using namespace std; const int MAX = 1000000 + 1; int N; int arrowHeight[MAX]; //화살 높이 /* int balloonHeight[MAX]; //풍선 높이 bool popped[MAX]; //풍선이 터졌는지 여부 int minArrow(vo..