문제풀기이야기 (19) 썸네일형 리스트형 2110번_공유기 설치_BOJ 문제 링크2110번 공유기 설치 : https://www.acmicpc.net/problem/2110 문제 설명 및 해결 아이디어좌표의 범위가 최대 1,000,000,000이여서 시간초과가 난다.그래서 Parametric Search로 해결할 수 있다.mid값을 간격으로 설정한다.설치한 공유기 개수가 주어진 공유기 개수 C보다 크거나 같을 경우, mid를 크게하여(간격을 크게하여) 공유기 개수를 줄일 수 있다.반대의 경우, mid를 작게하여 공유기 개수를 늘릴 수 있다. 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include using namespace std;#define ll lo.. 1300번_K번째 수_BOJ 문제 링크1300번 K번째 수 : https://www.acmicpc.net/problem/1300 문제 설명 및 해결 아이디어이 문제를 그냥 구현하게 되면 시간초과가 난다. Parametric Search로 해결할 수 있다.mid값은 1부터 K까지의 범위안에서 움직여주자. 이 문제를 풀기 위해서는 다음의 내용을 알아야 한다.즉, 특정한 mid값은 mid이하의 수의 개수가 주어진 K개 이상이면서 가장 작은 수가 된다. 코드12345678910111213141516171819202122232425262728293031#include #include using namespace std;#define ll long long intll n, k, res;void func() { ll left = 1, right.. 2512번_예산_BOJ 문제 링크2512번 예산 : https://www.acmicpc.net/problem/2512 문제 설명 및 해결 아이디어Parametric Search문제이다.mid는 배정할 예산으로 설정한다.문제의 요구대로, 각 지방의 예산요청액이 배정할 예산액보다 클 경우 예산액을 더해준다.반대의 경우, 예산요청액을 더해준다.그 합이 주어진 총 예산인 M보다 작거나 같을 경우, mid를 크게해준다.반대의 경우, mid를 작게하여 M과 비슷해지도록 합을 작게 해준다. 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include using namespace s.. 1654번_랜선 자르기_BOJ 문제 링크1654번 랜선 자르기 : https://www.acmicpc.net/problem/1654 문제 설명 및 해결 아이디어Parametric Search문제이다.이때 right는 10,000,000,000으로 해야한다.mid는 랜선 길이로 설정한다.특정 mid값으로 만들 수 있는 랜선의 개수가 주어진 N보다 작을 경우, mid값을 작게하여 랜선의 개수를 늘릴 수 있다.반대의 경우, mid값을 크게하여 랜선의 개수를 줄일 수 있다. 코드123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include using namespace std;#define MAX_S 10001#defi.. 6236번_용돈 관리_BOJ 문제 링크6236번 용돈 관리 : https://www.acmicpc.net/problem/6236 문제 설명 및 해결 아이디어Parametric Search문제이다.left의 범위는 이용할 금액중 가장 큰 값부터 시작하면 된다.mid는 인출 할 금액 K로 설정한다.특정 mid값으로 인출한 횟수가 주어진 M보다 클 경우, mid값을 크게하여 인출 횟수를 줄인다.반대의 경우, mid값을 작게하여 인출 횟수를 늘릴 수 있다. 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include using namespace std;#define ll long long int.. 2343번_기타 레슨_BOJ 문제 링크2343번 기타 레슨 : https://www.acmicpc.net/problem/2343 문제 설명 및 해결 아이디어Parametric Search문제이다.left의 범위는 레슨 중 가장 긴 길이부터 시작하면 된다.mid를 lesson길이로 설정한다.만들어진 블루레이 개수가 M보다 클 경우, mid를 크게하여 블루레이 개수를 줄인다.만들어진 블루레이 개수가 M보다 작거나 같을 경우, mid를 작게하고, 이때의 mid값 중 최소값을 저장한다. 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include using namespace std;#define ll lon.. 2805번_나무 자르기_BOJ 문제 링크2805번 나무 자르기 : https://www.acmicpc.net/problem/2805 문제 설명 및 해결 아이디어나무의 수 N은 1이상 1,000,000이하이다. 그리고 가져갈 나무의 길이 M은 1이상 2,000,000,000이하이다. 가장 간단하게 완탐을 하게 되면 O(NM)이 되어 시간초과가 난다.이를 효율적으로 하기위해 Parametric Search로 해결할 수 있다.그리고 이 문제의 비교함수 y=f(x)의 관계를 생각해보면, 다음과 같다. 즉, SUM이 커질수록 가져갈 나무의 길이 M이 작아지는 관계이다. 이를 잘 생각하여 코드를 작성해야한다. 코드12345678910111213141516171819202122232425262728293031323334353637383940414.. 1072번_게임_BOJ 문제 링크1072번 게임 : https://www.acmicpc.net/problem/1072 문제 설명 및 해결 아이디어주어진 게임횟수는 최대 1,000,000,000이다. 시간초과가 날 수 있기 때문에 Parametric Search로 접근해야 한다. mid를 게임횟수로 설정하여, 승률(Z)이 변할 때의 mid의 최소값이 문제의 출력이된다. 코드12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std;#define ll long long int#define INF 9999999999999999 ll total, win;ll originRatio, newRatio;ll f.. 이전 1 2 3 다음
