DP를 활용한 문제이다. 동적 계획법을 활용한 문제는 메모이제이션(Memoization)을 활용하여 반복되는 계산을 줄이고 완전탐색을 할 것인지 구조를 잡는 것이다. 이 문제에서 i번째 물건까지를 handling하면서 총 V의 부피를 할당했다고 했을 때 max value를 저장해두면 dp[i][j] = dp[i -1, j] 와 dp[i - 1, j - i번째 부피] + i번째 value 중 최댓값을 저장해두면 된다. (특히 array의 index와 정보를 매칭하는 아이디어는 잘 기억해두도록 하자.) 즉, 전후 참조하는 것이 아니라 index가 더 낮은 부분만을 참고하면서 위로 올라가는 형태이므로 DP로 처리하기에 적합하다. 단, 이 문제에서 주의할 지점은 가장 Base case에 대한 처리인데 맨 바닥은..

어려워 보일 수 있으나 도형적으로 센스를 발휘하면 쉽게 구할 수 있다. 위의 발문에서 제시한 것처럼 각 다각형은 여러개의 삼각형으로 찢어서 생각할 수 있다. 그러한 측면에서 바라본다면 각각의 도형은 작은 도형의 모임으로 생각할 수 있고, 이 측면에서 DP를 읽었으면 충분하다. 그러면 각각의 경우에 대해서 상황을 재분석하면 다음과 같다. 꼭짓점이 홀수인 경우에는 결과적으로 삼각형을 하나 띄고 생각해보면 삼각형 1개와 꼭짓점이 짝수인 도형의 합으로 생각할 수 있다. 꼭짓점이 짝수인 경우에는 결과적으로 삼각형을 하나 띄고 생각해보면 삼각형 1개와 꼭짓점이 홀수인 도형의 합으로 생각할 수 있다. 그런데, 꼭짓점이 짝수인 경우에는 삼각형의 가장 맞은편에 꼭짓점이 존재하고 이를 기반으로 도형은 대칭적으로 나눠지고 ..

이 문제의 경우는 모든 떨어진 거리가 정수인 것에 대하여 등차수열 관계가 이루지 못하게끔 하는 최솟값을 물어보는 것이다. 최솟값을 구해야하기 때문에 불가능한 것들을 모두 지우고 나머지 중에 최소를 구하는 것이 가장 현실적인 것을 깨달아야 한다. 그러면 문제에서 0~ 1000까지라고 하였으므로 배열을 미리 0~ 1000까지 설정하고 에라토스테네스의 체 논리처럼 슥슥 지워나가는 방향으로 하는 것이 가장 타당하다고 생각해야 한다. 또한, 고등학교때 배운 것처럼 등차수열의 3개의 항의 관계는 중앙값의 2배가 양 옆 수열의 합과 같다는 것이다. 이를 기반으로 불가능한 후보를 확보할 수 있다. 이 과정에서 이전 수열들에 대한 정보가 필요하게 되므로 이 지점에서 DP가 유리하다는 것을 인식하면 된다. 이를 기반으로 ..

상당히 어려운 문제이다. 이 문제를 보고 DP를 느끼는 것이 매우 어려운데, 각각의 타이밍마다 선택하는 기준이 앞의 선행조건에 의해 영향을 받는다는 점에 착안하여 DP 문제임을 인지하면 된다. 예를 들면 N시에 어떠한 광물을 채굴할지의 여부는 일단 전체 집단에서 N시에 끝나는 지를 확인하고 없으면 N-1시 까지의 최대 최굴량과 동일하다. 만약 존재하는 경우, 해당 시작시간이 M이라 가정하면 N - M시의 최대 최굴량에서 추가되는 최굴량을 더해준 것과 같다. 만약 N시에 끝나는 경우가 많은 경우에는 최댓값을 기준으로 결정해주면 된다. 즉, N시에서의 최대 최굴량을 구하는 과정에서 N.- M시의 최대 최굴량이 들어가게 되므로 DP를 활용하면 쉽게 구할 수 있음을 이 과정에서 느껴야 한다. // 다만, N시에..

이 문제를 보고 가장 먼저 접근한 방식은 문제에서 시키는 것처럼 (1, 1)에서부터 하나씩 경우의 수를 새어나가는 것이다. 마치 초등학교때 격자 모양이 그려진 도착하는 경우의 수를 찾는 것처럼 새는 것이다. import sys def path_finder(x , y): global n cal = data[x][y] # Early exit if x == n and y == n: return data_store[n][n] # Normal process if x + cal