enginner_s2eojeong

N개의 랜선을 만들 수 있는 "최대" 랜선 길이를 찾아야 한다. (단조성을 띈다 -> 이분탐색으로 결정) 이분 탐색의 탐색 범위를 설정할 때, 최소 길이는 1, 최대 길이는 입력된 랜선 중 가장 긴 길이로 설정한다. 이후 mid 길이로 랜선을 잘랐을 때 총 몇 개가 만들어지는지 계산한 후,만약 N개 이상 만들 수 있다면더 긴 길이로도 가능할 수도 있으므로 l = mid + 1ans에 mid값 저장해놓고 계속해서 탐색 (가능한 최대 길이가 되도록)만약 N개 미만이라면mid 가 너무 길어 랜선 개수가 부족하기 때문에 r = mid - 1#include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie..

이 문제의 핵심은 단조성이다. 단조성이란 어떤 값이 계속 증가하거나 감소하는 성질을 의미한다.이 문제에서 우리가 찾고자 하는 것은 M개의 풍선을 만들기 위한 최소 시간인데 그 시간을 기준으로 보면 "어떤 시간 t에서 가능했다면, 그보다 더 큰 시간에서도 가능하다" 는 규칙이 성립한다.t 시간 안에 M개의 풍선을 만들 수 있다면,t+1, t+2, ... 같은 더 큰 시간에서도 M개 이상을 만들 수 있다. 이런 특성을 보일 때, 단조성을 띈다고 한다. 따라서 이 문제는 답이 단조 증가하는 특성이 있으므로이분 탐색을 적용하면 O(log T * N) 의 시간 복잡도로 해결할 수 있다. 1. 시간의 범위를 설정최소 시간 l = 1최대 시간 r = 10^12 (최악의 경우 -> 어떤 사람이 1개의 풍선을 만드는데 ..

문제의 핵심은 주어진 색종이를 같은 색으로만 이루어진 작은 종이들로 쪼개고, 각각 몇 개가 나오는지 세는 것.분할 정복으로 해결해봤다. 먼저, divConq라는 재귀 함수를 정의했다.이 함수는 현재 보고 있는 영역이 한 가지 색으로 이루어져 있는지 확인한다.만약 모두 같은 색이라면, white 또는 blue 개수를 증가시키고 끝낸다.아니라면, 색이 섞여 있다는 뜻이므로 4등분 해서 다시 검사한다.그렇게 해서 최종적으로 하얀색 종이와 파란색 종이의 개수를 출력하면 끝이다. 사실 난이도가 높지않은 문제지만 분할 정복을 처음 접하는 사람들에게 입문용으로 추천..!#include #include using namespace std;int white=0, blue=0;void divConq(vector>& pap..

[코드]#include using namespace std;int main(){ string word; int arr[26]; int k, cnt[26]={0}; for(int i=0; i> word; for(int i=0; i [해설]arr[26] 배열은 알파벳 26자 각각이 입력받은 단어에 포함되어 있는 경우 해당 문자의 위치를 출력하기 위해 선언했다. 알파벳이 입력받은 문자에 없을 때는 -1을 출력해야하므로 그냥 처음부터 -1로 싹 다 초기화 하고 시작했다. 사용자로부터 입력받은 단어에서 첫 글자부터 마지막 글자까지 for문을 돌면서 ASCII 코드를 이용해 각 알파벳이 알파벳 'a'와의 차이(10진수)만큼이 arr 배열에서의 index가 된다. 그리고 입력받은 word ..

[1차 코드]#include #include #include using namespace std;int main(){ int height[9], sum=0; for(int i=0; i> height[i]; sum+=height[i]; } sort(height, height+9); int i, j, I, J, t=0; for(int i=0; i arr; for(int k=0; k [해설]한국정보올림피아드 초등부 문제였다는데 내가 아직 코린이라 처음엔 틀린 답이 계속 나왔었다... 흑흑9명의 난쟁이들의 키를 for문에서 입력값으로 받아 height[] 배열에 저장과 동시에 sum에도 누적합을 구해놓았다. 이후 height 배열을 sort를 사용해서 오..

[코드]#include using namespace std;int main(){ int L, P, num[5]; cin >> L >> P; for(int i=0; i> num[i]; } int a=L*P; for(int i=0; i [해설]5개의 신문사로부터 수집한 참가자의 수에서 상근이가 계산한 참가자의 수를 빼서 출력하면 됐던 쉬운 문제. 출처: https://www.acmicpc.net/problem/2845

[코드]#include #include using namespace std;int main(){ int N, num[100000]; cin >> N; for(int i=0; i> num[i]; } sort(num, num+N); for(int i=0; i [해설]어제 푼 단어 정렬 복습 차원에서 일부로 비슷한 문제를 골라왔다. c++ 내장함수인 sort를 이용해서 숫자를 오름차순으로 정리한 후,for문을 이용해서 출력하되, 같은 숫자가 반복되는 경우에는 continue를 이용해 한번만 출력되도록 했다.어제 풀었던 단어 정렬 문제에서는 특수한 조건이 붙어 sort에 추가적으로 compare이라는 사용자 함수를 적용하도록 했지만이번 문제에서는 단순히 오름차순으로만 정렬하면 되..