순간을 성실히, 화려함보단 꾸준함을

www.acmicpc.net/problem/11663 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 문제 : 점들이 N개 주어지고 M개의 선분이 주어질때 각 선분들에 점들이 몇개가 포함되어있는지 구하시오 해설 : 각점들마다 일일이 l n >> m; for (int i = 0; i > A[i]; sort(A, A + n); for (int i = 0; i > x >> y; if (y < A[0] || A[n - 1] < x)cout

www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net 문제 : 징검다리를 건너기 위해 점프를 하는데 x 칸을 점프했으면 다음에는 x보다 더 큰 칸을 점프해야 합니다. 이때 처음은 몇칸을 뛰던 전혀 상관이 없습니다. 그러나 반드시 N번째 징검다리는 도달해야 합니다. 이때 최대한 징검다리를 많이 건널때 개수를 구하시오 해설 : 먼저 가장 많은 징검다리를 건너기 위해선 어떻게 해야될까요???우린 한번 가정을 해봅시다. 만약 n이 9이고 처음 4칸을 뛰었다고 해봅시다. 그러면 다음에 뛸때는 무조건 4칸보다 더 많이 뛰어야 하고 반드시 9번째 징검다리에 도달을 해야하니 5칸을 뛰..

www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 문제 : 배열1이 주어지고 배열2가 주어질때 배열 1에 배열2의 수들이 존재하는지 여부를 구하여라 해설 : 기초적인 이분탐색 문제입니다. 오랜만에 sort를 직접 구현했습니다. 안짜게 되면 당연스럽게 까먹더라구요. 그래서 상기좀 시킬겸 mergesort를 구현했습니다. #include using namespace std; int arr[(int)1e6],num[(int)1e6]; void solve(); void m..

www.acmicpc.net/problem/20551 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net 문제 : 배열 A가 주어지고 이를 정렬한 배열을 B라고 할때, 주어진 쿼리마다 각 값들이 B의 배열에서 어느 위치에 있는지 출력하여라 해설 : 요새 이분탐색 문제만 쉬운것 부터 풀고있는 중입니다. A배열을 sort 한 후 이분탐색으로 위치를 찾아내면 됩니다. 그러나 '처음으로 등장한 위치'를 출력하여하기 때문에 low_bound가 되겠네요. 또한, 배열에 있지 않은 위치는 set을 사용해..

www.acmicpc.net/problem/2428 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net 문제 : 각 파일의 크기가 주어지고 F(i) =0.9xF(j) 인 쌍을 구하여라 해설 : 이분탐색 문제입니다. 이분탐색은 풀때마다 헷갈리는 것 같아요 ㅠㅠㅠ 앞으로 꾸준히 풀 생각입니다. 먼저 n의 범위를 보고 우린 모든 가능한 경우의 수를 할 수 없다는 것을 알 수 있습니다. 그럼 다른 방법을 사용해야 되는데 조건을 보면 정렬해서 이분탐색 하..

www.acmicpc.net/problem/2417 2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 : n이 주어지고(n> n; cout

www.acmicpc.net/problem/14931 14931번: 물수제비 (SUJEBI) 급격한 기후변화로 최근 대곽나라의 많은 강에서 생태계 교란종이 나타나고 있다. 이에 대곽나라의 이기범 대통령은 국무회의를 주재해 정부 차원의 대책을 논의하게 되었다. 대통령, 국무총리 www.acmicpc.net 문제 : 수들이 주어지고 각 간격 만큼 점프하여 수들을 더했을때 가장 최대값이 되는 수를 구하여라 해설 : L의 범위가 최대 백만이니 1부터 L까지 점프해서 일일히 구해준다고 생각해 봤을때의 시간복잡도는 O(L/1 + L/2 + ..... + L/L-1 + L/L) 이 되겠죠. 충분히 2초안에 들어올 수 있는 시간입니다. #include using namespace std; using ll = long ..

www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 문제 : 3으로 나누어 떨어지면 나누고, 2를 곱하는 동작을 한번 할 수 있습니다. 이때 n 개의 정수가 주어질때 이 n개의 정수를 적절히 나열하여서 규칙에 맞게 순서를 정해주세요 해설 : 먼저 문제에서 항상 답은 존재한다고 했으니 예외상황에 대해선 굳이 생각할 필요가 없겠죠. 그럼 단순하게 생각해봤을때 모든 가능한 경우의 수를 해보면 됩니다. 단, 조금 신경써서 펙토리얼을 사용할 수는 없다는..

www.acmicpc.net/problem/14256 14256번: SSR 첫째 줄에 N, M이 주어진다. (1 ≤ N, M ≤ 77,777) www.acmicpc.net 문제 : SSR(A, B) = (sqrt(A) + sqrt(B))^2 이라고 하고 1

www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 : 그래프와 간선이 주어지고 꼭 거쳐야 할 두 정점이 주어질때 1->N 까지의 최단거리를 구해라 해설 : n=800이니 그냥 플로이드-와샬 알고리즘을 사용해서 구해줬습니다. 꼭 거쳐야 할 정점이 a,b 라면 min(1->a->b->N,1->b->a->N) 이 답이 되겠죠. 도달할 수 없는 부분을 따로 예외처리 해주시고요. #include using namespa..

www.acmicpc.net/problem/1407 1407번: 2로 몇 번 나누어질까 자연수 N이 주어지면, 자연수를 유지하면서 N을 2로 몇 번까지 나눌 수 있는지를 생각해 볼 수 있다. 즉, N의 모든 약수 중 2의 거듭제곱 꼴이면서 가장 큰 약수를 생각하는 것이다. 예를 들어 15의 www.acmicpc.net 문제 : f(n)의 정의가 주어지고 a와 b의 자연수가 주어질때 a~b까지 f(a)~f(b)를 구하시오 해설 : 자 이런 xxx같은 문제....(괜히 그러는 겁니다 저가 못나서) 한번 봐봅시다. 먼저 항상 단순하게 생각을 해봅시다. 그냥 a부터 b까지 전부 수들을 보면서 2로 나누어주고 개수를 세고 다 더하면 되겠죠. 그러나....항상 문제는 저희에게 편하게 풀도록 내버려 두지 않습니다. ..

www.acmicpc.net/problem/10246 10246번: 부동산 경매 각 테스트 케이스는 하나의 정수 N (1≤N≤1,000,000) 으로 이루어져 있으며 손님이 갖고 있는 돈을 나타낸다. 입력의 끝은 0으로 주어진다. www.acmicpc.net 문제 : 연속된 정수들의 합으로 주어진 수를 만들 수 있는 경우의 수를 구해라!!!! 해설 : 이런 문제....즉, '입력의 제한'을 고려해야 하는 문제가 은근히 자주 나오는 것 같습니다. 저도 해맸습니다. 일단 먼저 우린 '연속된 정수'들의 합이라는 조건이 달려있다는 것을 알 수 있습니다. 그럼 이것은 우리가 중학교??인가요???암튼 '시그마'라는 공식을 이용할 수 있겠죠. 시그마 (a~b) = 시그마(1~b) - 시그마(1~a) + b 그럼 먼저..