C++5 BOJ 1034 - 램프 https://www.acmicpc.net/problem/10341차 시도처음 그리디를 이용하여 0의 개수가 가장 많은 열을 스위치 작동시키는 방법을 구상했다.O(N*M)이 걸렸지만 스위치 작동 후의 0을 구하는 과정과 켜진 행을 찾는 구간 때문에 시간 초과가 발생했다.더 빠른 방법을 구상해보기로 했다.2차 시도우선 규칙이 보였다.한 행에서 0의 개수가 k보다 크면, 해당 행은 완전히 켜질 수 없다.한 행의 0의 개수와 k의 홀짝이 다르면, 해당 행은 완전히 켜질 수 없다.2번의 경우, 밑에 예시로 보자3 30101011014일 경우, 2번째 열을 홀수번 킬 때 2,3번 행이 완전히 켜지게 된다.그러나 k가 짝수이기 때문에 2,3번 행은 처음과 같은 상태가 된다.3 30101011013반면, k가 홀수가.. 2024. 10. 28. [그리디 #20] BOJ 2212 - 센서 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 접근방법 저번에 풀었던 행복유치원과 같은 문제이다. 예제 2번을 보면서 한번 살펴보자. 10 5 10 5 20 3 14 6 7 8 18 10 12 15 해당 센서를 오름차순으로 정렬하면 다음과 같다. 3 6 7 8 10 12 14 15 18 20 이 세선들을 몇 개씩 묶어서 총 K개의 묶음으로 만들면 된다. 이때, 문제의 핵심은 센서 사이의 거리가 짧은 것을 위주로 선택해.. 2024. 2. 25. [그리디 #8] BOJ 1758 - 알바생 강호 https://www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 접근 방법 그리디의 정석으로 풀 수 있는 문제 중 하나이다. 이 문제에서 주문금액 - (등수 - 1)의 공식을 이용해 최고의 팁을 받는 것이 문제의 끝이다. 별다른 조건은 없기 때문에 주문금액이 가장 큰 손님부터 받게되면 팁을 최대로 챙길 수 있다. 쉽게 접근할 수 있는 문제라고 생각한다. 구현 시, N이 최대 100,000, 팁이 100,000을 넘을 수 있기 때문에 타입 선정.. 2024. 2. 11. [그리디 #6] BOJ 1343 - 폴리오미노 https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 접근 방법 매우 간단한 그리디 문제이다. 저번에 풀었던 거스름돈 문제와 같은 풀이로 해결이 가능하다. https://parvegoongame.tistory.com/115 [그리디 #5] BOJ 14916 - 거스름돈 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 접근 방법 간단한 그리디 문제이다. 5원과 2원 뿐이기 때문에 5원을 빼야하는 경 meteorfi.. 2024. 2. 10. [그리디 #3] 카드 합체 놀이 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 접근 방법 예제를 보면 쉽게 해결할 수 있는 문제이다. 최종적으로 모든 카드의 합이 최소가 되어야 한다. 최소가 되기 위해선 당연하게 가장 작은 카드 2개를 선택하면 된다. 매우 간단하게 해결할 수 있는 그리디 문제이다. #include #include #include using namespace std; vector v; int n, m; int main().. 2024. 2. 5. 이전 1 다음
