baekjoon

풀이법 연속 합에서 가장중요한건 구간을 따로 몰라도 된다는 점이다. 이게 무슨말이냐면 우리가 구간의 합을 구할떄 무의식적으로 Left와 Right를 구할려고 한다. 그러면 자동적으로 n^2의 빅오를 가진 알고리즘이 탄생하게된다. 하지만 지금 현재까지 더한값이 0보다 작으면 최대값은 그대로 두고 0보다 크면 최대값을 갱신해주면 된다. 다음은 그 풀이이다. 1 2 3 4 5 6 더보기…

풀이법은 테이프를 붙이곳을 체크하고 테이프가 붙혀진곳이면 다음 터진장소로 이동한다. 코드는 다음과 같다. 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 #include <iostream> #include <algorithm> #include <vector> #include <cstring> bool arr[1200]; 더보기…

Tn = 1 + 2 + 3 + … + n = n(n+1)/2 이고 이 T의 3가지의 합으로 해당 숫자가 이 합에 들어가는가 안들어가는가를 물어보는 문제이다. 속도를 빠르게하기위해 T를 전부 구한다음 반복문을 이용해서 가능한 조합인 경우 체크표시를 해준다. 풀이는 다음과 같다.     1 2 3 4 5 6 7 8 더보기…

별거 아닌데.. 심심삼아..풀어보았다.. 전체적인 로직은 짝수는 2제외하고 전부 소수가 아니다. 홀수이면 해당값의 루트를 구하여 소수인지 판별한다. 에라토스테네스 체도 있지만… 이문제는 그런거 신경안써도..충분히 풀수 있고. isPrime만 있으면 쉽게 에라토스테네스체를 구현가능하다.   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 더보기…

이 문제는 일단 전부 교체해보지 않는한 최대값을 알수 없는 문제가 있다. 결국 브루트 포스 문제이다. 답은 아래와 같다. 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 더보기…

생성자 M이 N을 만들수 있다. N이 주어질경우 M을 찾아라 하지만 주어진건 N이기때문에 이를 딱히 찾을 방도가 없다. 그렇기 때문에 이문제는 무차별 대입으로 풀어야한다. 여기서 빅오를 줄일 방법이 존재하는데 M은 N보다 작다는 점이다. 왜냐하면 M은 N의 분해합을 하기때문에 작을수가 없다. 소스는 다음과 같다.   1 2 3 4 5 6 7 더보기…