코딩 다이어리

오랜만에 새해 다짐으로 했던 알고리즘 문제를 풀었다. 근데 첫 문제부터 난관.. 시작부터 나에게 고난을 준 문제는 아래에 있다. 이 문제를 보고 나는 DP라는 것을 알았지만.. 메모이제이션/냅색 방법이라고는 생각도 못했다.. 그래서 내가 처음에 도전한 방법은 한 무게당 n * n-1 * n-2 ... 개를 하나하나 비교해보는 방식이었다. 근데 이 방법으로 짜는 것도 java로 하려니 너무너무 어려웠다. C/C++ 에서는 지역 변수가 따로 있어서 가능 할 것 같았는데, 여기서는 지역도 전역처럼 되어 버려서.. 너무 어려워@_@ 내가 생각해낸 코드이다. 근데 이 코드가 안되서.. 조금 더 수정하면 될 것 같아서 아직 가지고 있는 중이다.. 수정해봐야지~! 그 후에 고민해보다가 구글링을 통해 알고리즘을 찾았다..

이 문제는 거의 2일? 적게 생각하긴 했지만.. 계속 생각해도 생각이 나지 않아 엄청 답답해 하고 있었다.. 그러다 결국 오늘 글을 쓰기 위해 유튜브를 급히 보았다. 세상.. 엄청 똑똑하신 분들이 많던데.. 보다가 엄청 띠용하는 분의 영상을 보고 설명을 해보고자 한다. DP란 결국 규칙성을 찾는 문제인데 규칙성 찾기가 너무나 어렵다 ㅠㅠ 우선 문제는 다음과 같다 가장 적은 개수의 봉지로 설탕을 나누기 위해서는 5봉지가 많아야 된다. 그래서 설탕을 5개씩 나열해보면 위 그림과 같이 나열 할 수 있다. 그럼 5개로 나누었을 때 경우의 수는 설탕이 0개, 1개, 2개, 3개, 4개가 남는 경우가 있다. 그림으로 표현하면 이러한 경우가 있다. 이때를 봉지로 계산해보면! 한개의 설탕이 남는 경우, 위와 같이 5개..