백준 재활 겸 KOI 준비 겸 라이(kks227)님의 알고리즘 강의를 밀고 있다. 그리디 밀면서 오늘 푼 G5. https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 일단 입력을 보고 센서 좌표가 일직선으로 안들어와서 정렬부터 해줬다. 정렬 하고 보니 테스트케이스에서 3과 6 사이에 연결이 없어야 정답이 나오겠다는 생각이 들었다. 왜 3과 6 사이로 직관했나 생각해보니 3과 6사이의 간격이 가장 커서 뺐다는 결론에 도달했고 ..

처음 봤을때는 전구를 두번 켜고끄고 할필요가 없다는 내용을 떠올리고 무지성 브루트포싱을 시도했지만 바로 2^100 TLE 나만 모르는 웰논 풀이 윗줄에 대해서 비트마스킹 등으로 브루트포싱을 진행해주면, 그 아랫줄은 윗줄의 상태에 따라서 켜고끄고 여부를 결정할수 있다고 한다. 쭉 순회해가면서 처리하기. 구현자체는 그리 어렵진 않았다. https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net #include using namespace std; ..

랭작문제 정렬을 열심히 해주고 범위에 상관없이 가져갈수있는 책들 중 가장 앞번호만 가져가게 해주었다 모두가 앞번호를 가져가려 하고, 앞번호를 가져갈 수 있는 사람들부터 책을 나눠주게 되면, 가장 많은 수의 책을 나눠줄 수 있게 된다. ​ https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net #include #include #include #include using namespace std; bool chk[1010] = {0}; int n,m,a,b,c..

https://www.acmicpc.net/problem/18186 18186번: 라면 사기 (Large) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i �� www.acmicpc.net 이 문제는 바로 앞 문제이기도 한 백준 BOJ 18185 - 라면사기 (Small) https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에 koder0205.tistory.com 이 ..

https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i �� www.acmicpc.net 딱 보자마자 그리디인건 알았는데 코너케이스랄까 조금 예외가 되는 케이스가 있어서 많이 고생했던 문제 라면을 하나 가져올때보다 두개 같이사는게 싸고 두개보다 세개를 살때가 더 싸므로 그리디로 생각했을때 가장 먼저 생각나는 풀이는 그냥 살수있는만큼 최대한 사는거였다. 그런데 질문창에도 있는 대표적인 반례인 1 2 1 1 같은 경우에서는, 세개 사고 0 1 0 1 이 되어 총가격..