https://www.acmicpc.net/problem/12797 12797번: 연금술 첫 줄에 정수 n과 m(1 ≤ n ≤ 109, 1 ≤ m ≤ 103)이 공백으로 구분되어 두고 주어진다. 다음 줄에 a1, a2, ..., am (1 ≤ ai ≤ 109)이 공백으로 구분되어 주어진다. www.acmicpc.net 고생 고생 끝에 겨우 풀었다. 정리해둘만한 내용이 많은 문제인 것 같아서 풀이를 기록해 둠. 우선 점화식부터 유도해보자. $ DP(n, m) $ 을 $1 \dots m $ 번 까지의 재료를 써서 $ n $ 개 조합할 때 만들 수 있는 완성품 품질의 총합이라고 정의한다. 이 경우 $ DP(n, m) $의 점화식은 다음과 같이 세울 수 있다. $$ DP(n, m) = a_m \cdot DP(n..
[2020-09-23] Codeforces Round 666 (Div.1)
오늘도 망했다. C를 대회 끝나고 30초 뒤에 제출해서 맞았고.. B는 풀지를 못했다. 왜 B같은 유형은 도저히 풀리질 않을까.. 잘 풀리다가 다시 연속으로 말아먹으니 멘탈이 너무 깨진다. A. Multiples of Length 어떤 수에 (x+1)을 더하면 x로 나눈 나머지는 1만큼 증가한다. 따라서, 전체 구간(1 ~ n)을 잡고 (n-1)로 나눈 나머지가 0이 되게 전체 값을 조정해준다. 그 다음 1 ~ n -1 / 2 ~ n 구간을 잡고 전체 값이 0이 되게 만들면 문제를 해결할 수 있다. n = 1일때 예외를 잘못 처리했다가 한 번 틀렸다. 이런 실수 하면 안 되는데.. B. Stoned Game 이런 식의 케이스 분석 기반의 게임 문제는 도저히 풀지를 못 하겠다. 나올 때마다 못 푸는 듯. ..
[2020-09-21] Codeforces Round 664 (Div.1)
오늘도 말아먹었다. 흠.. A번에서 멍청한 실수 두 번한 건 아쉽긴 한데, B 못푼 건 그냥 실력이어서 별로 할 말도 없다. 필요한 관찰 다 해놓고 못 풀었다.. 갈 길이 멀다. A. Boboniu Chats With Du 값이 m보다 큰 것과 그렇지 않은 것을 구분해보자. m보다 큰 값이 하나도 없는 경우 전체 합이 곧 답이 된다. m보다 큰 값이 하나라도 있는 경우, 그 개수를 c라고 하자. 하나를 고를 때마다 최대 d개의 다른 원소를 쓰지 못하게 할 수 있으므로, c개중에 (c + d) / (d + 1)개는 반드시 답에 포함이 되어야 한다. 이 값을 x라고 하자. m 보다 큰 걸 x ~ c개 쓰는 각각의 경우에 대해 값을 구해서 그 중 최댓값을 취하면 된다. 이 때 c개 중 k개를 쓴다고 가정했을 ..