가을의 개발 일지

서론별 건 아니고, 샤워할 때 간단한 문제나 하나 풀고 있자~ 생각하면서 백준 14606번 피자 (small) 문제를 보고, 씻고 있었다. 대충 $N$개의 피자판이 쌓여 있을 때, 피자판을 둘로 나눈다. 예를 들어, $N$이 8이면 4와 4, 혹은 3과 5처럼 나눌 수 있다.이때 나눠진 피자판의 개수를 서로 곱하면 즐거움이 나온다. 이걸 더이상 나눌 수 없을 때까지 반복한다. 피보나치 저리가라 할 기초적인 DP 문제라 문제 자체는 쉬웠는데, 간단한 암산으로도 아래처럼 풀 수 있었다. 일단 즐거움이 제일 커져야 하니까, N를 2로 나눠서.... 그리고 곱한 값에 각 칸의 수를 더하면.... 거기서, 갑작스레 든 의문. 왜 어떤 수를 쪼개서 곱할 때, 최댓값은 항상 균등할 때 나올까?원리를 몰라도 습관..

문제https://www.acmicpc.net/problem/25419 알고리즘 문제는 매일 풀고 있지만, 그때마다 항상 블로그를 쓰진 않았다.이전에 비슷한 걸 풀어서 쓸만한 내용이 없거나, 혹은 이동 중에 휴대폰으로 풀 때도 있어 글을 쓸 환경이 아닐 때도 있었으니까. 그래서 DP 문제를 여럿 풀면서, 원래대로라면 풀기만 하고 올릴 생각은 없었는데... 꽤 골때리는 문제를 만나 이렇게 포스팅한다.1. 첫 번째 풀이사고 과정가장 처음까지 돌아가면, 문제 조건이 엄밀하지 않아서 애를 먹었었다. 잘못 만든 문제다 이거.문제엔 단순히 "두 명의 학생이 규칙에 맞게 플레이했을 때"라고만 쓰여 있는데, 정확히는 최선의 방법으로 플레이했을 때가 되어야 한다. (대충 플레이하면 정답은 0일 수도, 1일 수도 있는 슈..