체뚱로그

풀이 시간: 01:59:18 시간 복잡도: O(nm) → 총 n * m개의 (n, m) 쌍을 계산 공간 복잡도: O(nm) → 2차원 배열 참고 https://kmiiiaa.tistory.com/20 https://sdy-study.tistory.com/210 문제 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다. 각 구간은 한 개 이상의 연속된 수들로 이루어진다. 서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다. 정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다. N개의 수들이 주어졌을 때, 답을 구하는..

풀이 시간: 01:58:30 시간 복잡도: O(21n) → O(n) : 숫자의 개수 n개와 가능한 결과의 범위가 0~20 (상수항 무시) 공간 복잡도: O(21n) → O(n) : 2차원 벡터 크기 n * 21 (상수항 무시) 참고: https://velog.io/@lacram/C-백준-5557번-1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서..

풀이 시간: 02:17:06 시간 복잡도: O(n√n) -> n에 대하여 n 이하의 모든 제곱수에 대한 연산 수행 공간 복잡도: O(n) -> 크기 n인 배열 dp 참고 https://beginnerdeveloper-lit.tistory.com/55 https://hongjw1938.tistory.com/47 https://ip99202.github.io/posts/백준-17626-Four-Squares/= 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는..