Problem Solving/Atcoder (3) 썸네일형 리스트형 AtCoder: ABC 180 D atcoder.jp/contests/abc180/tasks/abc180_d D - Takahashi Unevolved AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 곱셈과 덧셈을 통해서 숫자를 키워줄 수 있고, 상한선을 넘지 않는 한에서 가장 많은 횟수의 연산을 하여야 한다는 것이 문제의 조건이다. 곱셈을 하면 숫자가 급격히 커지므로, 일정 수 이상이 되면 (혹은 아예 처음부터) 곱셈을 한 결과는 항상 덧셈을 한 결과보다 크게 된다. 즉, 곱셈을 먼저 할 수 있는 만큼 하고(그나마 처음에 숫자가 작을 때) 곱셈을 한 결.. AtCoder : ABC 178 D - Redistribution atcoder.jp/contests/abc178/tasks/abc178_d D - Redistribution AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 이 문제 역시 대표적인 형식의 DP문제이다. 앞선 포스팅에서 살펴본 간단한 DP문제들은 이전 히스토리에서 한 개나 두 개 정도를 참조하여 현재의 값을 구하였다 (기본 피보나치 수열은 이전 값 2개를 참조하여 현재의 값을 구한다). 하지만 이번에는 꽤나 많은 값을 가져와야 한다. 수열의 합이 S가 되고, 각 수는 3이상이므로 첫 수는 항상 3부터 시작해서 따져봐도 좋다.. AtCoder : ABC 178 C - Ubiquity atcoder.jp/contests/abc178/tasks/abc178_c C - Ubiquity AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp DP문제이다. 점화식을 파악할 수 있다면 쉽고 간단한 문제겠지만, 그게 떠오르지 않는다면 역시 어렵다... 이러한 문제에 대해 어떻게 접근해야 할까? 이전 포스팅들에서 꾸준히 얘기하고 있지만, 필자가 이해하는 동적계획법(DP) 적용의 근거는 어떠한 정점(상황)에서 일정한 규칙을 적용하여 일정한 간격만큼 떨어진 다음 정점으로 넘어갈 때에 있다. 어떠한 정점에서 연결된 정점이 한 .. 이전 1 다음
