FandPROG FandPROG

문제 : https://www.jungol.co.kr/problem/1219 무엇을 구하는 문제인가? 한변이 k인 정사각형 모양의 색종이 n개를 이용해 잘못칠해진 부분을 모두 가릴때, k의 최솟값을 구하는 문제이다. ​ 해결 전략 k를 mid로 생각해 푸는 간단한 이분탐색 문제이다. 입력받을때, 잘못칠해진 부분의 높이는 최댓값만 필요하며, 그 최댓값은 low로 한다. 입력받은 좌표를 x기준 정렬 후, 탐색 ​ 알고리즘 1. 최대좌표의 값 mx, my를 입력받는다. 그 후 색종이의 수 n과 얼룩의 수 m또한 입력받는다. 2. m개의 얼룩의 x값을 저장, y는 최댓값만 저장하며 입력받는다. 3. low = maxy값, high = 최대 x값으로 한다. 4. x좌표를 정렬한다. 4. low가 high보다 작은..

문제 : https://www.jungol.co.kr/problem/5170 무엇을 구하는 문제인가? n개의 나무가 주어졌을 때, k이상 높이의 부분을 모두 잘라내 붙여 길이를 m이상으로 만들려 한다. 이때 최소 k값을 구하는 문제. ​ 해결 전략 N범위가 1,000,000으로 굉장히 크다. 따라서 완전 탐색보다는 이분탐색이 좀 더 좋아보인다. 찾아야되는 k값을 이분 탐색을 통해 찾으면 된다. ​ 알고리즘 1. n과 m을 입력받고, n개의 나무의 높이 arr을 입력받는다. 2. low = 1, high = 가장높은 나무의 높이로 선언한다. 3. low 가 high보다 작거나 같은동안 반복 -mid = (low+high)/2 -mid_res는 k에 mid가 들어갈 경우의 모두 잘라붙인 길이로 선언한다. -..

문제 : https://www.jungol.co.kr/problem/5805 무엇을 구하는 문제인가? 이미 X번 던져 Y번 앞면이 나왔다. 이때 몇번 앞면이 나와야 확률이 바뀌는 지 최소 횟수를 구하는 문제. ​ 해결 전략 -n범위가 굉장히 큼으로 완전 탐색은 불가능하고, 이에 따라 이분탐색을 생각해볼 수 있다. -현재 확률인 (y*100)/x를 변수now_p에 저장하고, ((y+mid)*100)/(x+mid)가 now_p에 근사할때 까지 이분탐색을 진행한다. ​ 알고리즘 1. x, y를 입력받는다. 2. (y*100)/x를 변수now_p에 저장한다. 3. 2분탐색에서 필요한 low = 1, high = 2e9(20억 = 최대입력값의 2배)로 선언한다. 4. low low = mid + 1 -아니면 ->..

문제 : https://www.jungol.co.kr/problem/1092 무엇을 구하는 문제인가? X의 Y제곱을 20,091,024로 나눈 나머지를 구하는 문제이다. ​ 해결 전략 -y를 반으로 나누어 결과값을 곱하면, x의 y제곱을 구할 수 있다.(ex. 2^4 = 2^2 * 2^2) -y를 계속 반으로 나누어 1이나온다면 x를 return하는 식으로 구현가능 -x, y범위가 크니 long long으로 자료형을 정하였다. ​ 알고리즘 1. x, y를 입력받는다. 2. Divide함수를 이용해, y를 분할하여준다. 3. 만약 y가 1이라면, x를 리턴 4. 해당함수의 리턴값을 출력하여준다. ​ ※주의 할점 y가 0인경우를 고려해야함 ​ #include long long Divide(long long ..