SH

BOJ Link https://www.acmicpc.net/problem/1229  풀이 과정런타임 전의 전처리 + DP 문제이다. 알고리즘 문제의 분류로서 런타임 전의 전처리란,솔루션 코드를 실행하기 이전에, 사전 작업을 통해 런타임 시 효율을 높히는(시간복잡도를 줄이거나 메모리 효율을 높히는) 문제를 뜻한다. 이 문제에서, N 100만 이하의 N에 대해 모든 육각수를 구하는 과정을 전처리로 실행할 수 있다. 이는 곧 707개의 경우가 나온다. 이를 바탕으로 100만 길이의 dp[]를 갱신한다면,O(707*100만) = 7억의 시간복잡도가 나온다. 문제의 제한이 2초기에, 나는 해당 코드가 통과하지 못할 것이라고 예상했다. 그래서 100만 길이의 배열 출력을 코드에 copy&paste하여 O(1)로 출..

BOJ Link https://www.acmicpc.net/problem/1758  풀이 과정순서에따라 받을돈에 0..-1..-2..-(N-1) 원이 차감된다. 이 때 합(받을돈-차감된 돈)이 음수일 경우, 0으로 치기 때문에 그리디하게 풀 수 있다. 그렇지 않다면 순서에 상관없이 똑같은 돈을 받을 것이다. 따라서, 내림차순으로 정렬하여 합을 누적하고 출력한다. 제출 코드#include #include #include #include int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int N; std::cin >> N; std::vector vec(N); for (int i = 0; i > vec[i]; } sort(vec..