반응형 분류 전체보기53 백준 28257번 : 알록달록 초콜릿 만들기(C/C++) 백준 28257번 공식 해설을 참고하여 작성된 풀이입니다. n번째 민트 초코는 어떤 수인지 구하는 문제이다. 브루트 포스는 당연히 시간 초과가 날 것이다. 규칙을 찾기위해 R번째 줄에 몇개의 민트 초코가 있는지 고찰해보면 줄마다 1, 0, 1 / 2, 1, 2 / 3, 2, 3 / 4, 3, 4 개의 민트초코가 있다는 사실을 알 수 있다. 3k번째 줄까지의 민트 초코의 개수를 살펴보면 등차 수열의 합이다. 이분탐색을 이용하여 n 1; ll y = mid*(3*mid+1)/2; if(y 2023. 6. 30. 백준 23760번 : 까다로운 아이들과 선물상자(C/C++) 백준 23760번 2243번 사탕상자와 비슷한 문제이다. 풀이의 핵심은 bi번째로 사탕수가 많은 상자를 선택해야한다. 세그먼트 트리를 이용하면 log n만에 선택할 수 있다. 배열의 index가 "사탕수"이고, value는 동일한 사탕수가 담긴 "상자의 개수"라고 해보자. 예를 들어 사탕수가 5개가 담긴 상자가 1개 있다고 하면 arr[5] = 1이다. 이 배열을 세그먼트 트리로 만들어주면 된다. 트리의 리프 노드에는 사탕수가 x인 상자의 개수가 저장되있을 것이다. query라는 함수는 트리에서 cnt번째로 사탕수가 많은 index를 찾아주는 함수이다. 만약 cnt 2023. 6. 1. 백준 1891번 : 사분면 (C/C++) 백준 1891번 문제를 해결하기 위한 단계는 아래와 같다. 1. 주어진 사분면에 해당하는 좌표를 찾는다. 2. 입력된 좌표만큼 이동한다. 3. 이동한 좌표의 사문면을 구한다. 만약 k번 쪼개졌다면 사분면의 개수는 2^k X 2^k이 된다는 사실을 이용하면 쉽게 해결할 수 있다. 주의할점 : 좌표평면을 벗어나면 -1을 출력해주어야한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #inclu.. 2023. 5. 30. 백준 4225번 : 쓰레기 슈트 (C/C++) 백준 4225번 백준 1708번 : 볼록 껍질 직관적으로 생각했을때, 쓰레기의 한쪽면이 쓰레기통의 벽에 닿아있는것이 최선의 경우이다. 오목한면은 해당되지 않음으로 우선 볼록 껍질을 구해준다. 다음 각각의 변에서 가장 거리가 먼 점까지의 거리중 가장 짧은 것을 구해주면 된다. 점 (x1, y1) 을 지나는 직선 ax+by+c = 0을 구한다음 점과 직선사이 거리 공식을 적용해주었다. 혹시나 부동 소수점 오차가 날까봐 d를 제곱한 값을 비교해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52.. 2023. 5. 17. 이전 1 ··· 9 10 11 12 13 14 다음 반응형
