https://www.acmicpc.net/problem/22354 22354번: 돌 가져가기 처음 위치 기준 왼쪽에서 $5,\ 6,\ 2,\ 3,\ 4,\ 7,\ 8,\ 1$번째 돌을 순서대로 가져가면 $3$번째 돌과 $5$번째 돌을 가져갈 때 점수를 얻어 $13$점이 된다. www.acmicpc.net 내가 푼 문제중 제일 티어가 높은 문제이다.. 게다가 그리디라 생각하기가 엄청 어려웠다 우선 돌을 최적으로 가져가는 방법에 대해 설명하겠다. 1. 연속된 돌은 반드시 1개만 가져갈 수 있다 (= 연속된 돌에서는 점수를 2번 이상 얻을 수 없다) -> 이 부분은 돌들을 그려놓고 한번 해보길 바란다. 이웃한 돌들이 색이 달라야 점수를 얻는데, 이웃한 돌이 같은 색이면 애초에 점수를 얻을 수 있는 환경이 아..
https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 풀이는 다음과 같다. 예시로는 200을 들겠다! 200 = 1 + 199이다. 199 = 2 + 197이다. (이미 1을 위에서 써버렸으므로 수를 1증가시키면서 사용) 197= 3 + 194이다. ... 계속하다보면 수가 계속 줄어들어서 45 = 18 + 27 까지 오게 되고 27 = 19 + 9가 되면서 뭔가 이상한 순간이 생긴다. 9는 아까 써버렸는데 또 9가 나온다. 27을 더이상 쪼갤 수 없으므로, 200은 1~18 그리고 27까지해서 총 19개의 자연수로 나눌 수 있다! 즉, 200을 덧셈으로 쪼개나가면서..
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 수를 2개씩 묶거나, 더해가면서 수열의 합 중 최대 값을 찾는 문제이다. 양수를 담을 벡터 하나, 0을 담을 벡터 하나, 음수를 담을 벡터 하나 총 3개의 벡터를 활용하였다. 양수는 내림차순으로, 음수는 오름차순으로 정렬해준 뒤, 최댓값을 계산하면 된다! 먼저 양수에서는, 나의 다음 숫자가 1인 경우가 중요하다. 양수는 거의 곱하는 것이 이득인데, 1일 때는 곱하는 것보다 더하는 것이 더 이득이..
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 이 문제는 입력의 범위가 좀 크기 때문에 그냥 O(N^2)으로 탐색하게 되면 시간초과가 발생할 수 있는 가능성이 존재한다. 그러면 어떻게 푸냐? 그리디 알고리즘을 이용하자! 1. 우선 입력을 받고, 2. 보석의 정보와 가방의 정보들을 오름차순(작은 것부터)으로 정렬해준다. 정렬할 때는 greater나 less를 사용해도 되지만, 비교..
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si pq; int n,s,t; /*bool compare(pair a, pair b){ if(a.first > n; for(int i=0;i> s >> t..
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 골드4티어 문제치고는 좀 쉽다는 생각이 들었다. 요즘 빡센 bfs 구현문제만 풀어서 그런가..? 싶지만 자만하지 말자.. 우선순위 큐를 하나 선언하는데, 기본 값은 내림차순(큰 값이 우선) 이므로 오름차순으로 정렬되도록 선언해준다! 그리고 제일 작은 것과 그 다음 작은 것 2개를 가져와서 더한 후, 다시 큐에 넣는다. 이 때 정답은 누적합으로 구해준다. 큐가 비거나 하나밖에 없다..
