풀이법 연속 합에서 가장중요한건 구간을 따로 몰라도 된다는 점이다. 이게 무슨말이냐면 우리가 구간의 합을 구할떄 무의식적으로 Left와 Right를 구할려고 한다. 그러면 자동적으로 n^2의 빅오를 가진 알고리즘이 탄생하게된다. 하지만 지금 현재까지 더한값이 0보다 작으면 최대값은 그대로 두고 0보다 크면 최대값을 갱신해주면 된다. 다음은 그 풀이이다. 1 2 3 4 5 6 7 8 9 10 11 소개 더보기 1912 연속합[…]
풀이는 간단하다 0행부터 n행값의 최소값만 저장하면되고 맨마지막 행의 최소값을 찾아 출력하면된다. 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 #include <iostream> #include <algorithm> #include <cstdint> #include <cstring> using namespace std; int saveDate[1000][3]; int dp[1000][3]; int main() 소개 더보기 1149 RGB거리[…]
풀이는 아래와 같습니다. 예로 입력으로 아래와 같은 값이 들어옵니다. 5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 저희는 Hamming Distance의 값을 최소하하는 점을 구하고 싶은거니 세로로 스캔하면서 가장 많은 문자가 있는 경우가 최소의 Hamming Distance을 만드는 문자가 됩니다. 풀이는 다음과 같습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 소개 더보기 1969 DNA[…]
풀이법은 테이프를 붙이곳을 체크하고 테이프가 붙혀진곳이면 다음 터진장소로 이동한다. 코드는 다음과 같다. 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]; using namespace std; int main() { int N, K; cin >> N >> K; std::vector<int> v; 소개 더보기 1449 수리공 항승[…]
Tn = 1 + 2 + 3 + … + n = n(n+1)/2 이고 이 T의 3가지의 합으로 해당 숫자가 이 합에 들어가는가 안들어가는가를 물어보는 문제이다. 속도를 빠르게하기위해 T를 전부 구한다음 반복문을 이용해서 가능한 조합인 경우 체크표시를 해준다. 풀이는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 소개 더보기 10448 유레카 이론[…]
별거 아닌데.. 심심삼아..풀어보았다.. 전체적인 로직은 짝수는 2제외하고 전부 소수가 아니다. 홀수이면 해당값의 루트를 구하여 소수인지 판별한다. 에라토스테네스 체도 있지만… 이문제는 그런거 신경안써도..충분히 풀수 있고. isPrime만 있으면 쉽게 에라토스테네스체를 구현가능하다. 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 소개 더보기 1978 소수 판별[…]
이 문제는 일단 전부 교체해보지 않는한 최대값을 알수 없는 문제가 있다. 결국 브루트 포스 문제이다. 답은 아래와 같다. 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 소개 더보기 3085 사탕 게임[…]
생성자 M이 N을 만들수 있다. N이 주어질경우 M을 찾아라 하지만 주어진건 N이기때문에 이를 딱히 찾을 방도가 없다. 그렇기 때문에 이문제는 무차별 대입으로 풀어야한다. 여기서 빅오를 줄일 방법이 존재하는데 M은 N보다 작다는 점이다. 왜냐하면 M은 N의 분해합을 하기때문에 작을수가 없다. 소스는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 소개 더보기 2231 문제 분해합 풀이[…]
깊이 우선탐색처럼보이지만 다른 방법으로도 쉽게 풀수 있다. 조합을 이용하는 것이다. 가짜를 뽑는경우의 수를보면 9c2이니 총 가지의수는 (9*8)/(2*1) 이 나오게 된다. 여기서 중요할점은 가짜를 제외하고 뽑을경우 총합이 100이 되면 가짜가 자동으로 나오게된다. 아래는 그 코드이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 소개 더보기 2309 문제 일곱 난쟁이문제 풀이[…]