7, 11, 17 크기의 상자를 이용해 케이크를 먹을 때 이 상자들의 조합으로 먹을 수 없는 가장 많은 케이크 수?
ex) 케이크 25개는 7짜리 2개, 11짜리 1개를 이용해 냠냠😋
처음 문제를 접했을 때는 어떻게 풀어야 할지 감이 오지 않아 보기의 문항들을 모두 확인해보는...😅
그래서, 해설을 참고하며 논리적으로 생각하는 과정을 이해한 후 정리해보았습니다.
먼저, 문제를 풀기 위해 다음과 같은 생각을 할 수 있습니다.
주어진 상자로 만들 수 없는 최대 수가 존재한다는 것은
결국, 어떤 수 N이 만들 수 없는 최대 수라면 N + 1, N + 2, ... 은 모두 만들 수 있는 수라는 것이다.
다음으로, 위 가정이 참이라는 것을 증명하기 위해 N + 1, N + 2, ... 이 모두 만들 수 있는 수라는 것을 증명하면 됩니다.
이에 대한 증명은 N + 1이 만들 수 있는 수라면 7, 11, 17 중 가장 작은 수인 7을 기준으로 하여 N + 7까지 연속한 7개의 수가 모두 만들 수 있는 수라면 증명이 완료됩니다.(N + 8부터는 7이 한 번씩 더 사용된 것이므로)
위 내용을 프로그래밍으로 옮겨 확인해봅시다!
위 알고리즘은 2가지 방식으로 구현할 수 있습니다.
그럼, 두 방식 중 어떤 것이 더 효율적일까요?
- 메모리 소모 : 1번 < 2번
- 수행 시간 : 1번 > 2번
2번 방법은 각각의 경우마다 dp테이블에 값을 기록하기 때문에 1번 방법보다 더 많은 메모리를 사용하게 됩니다. 하지만, 수행 시간 측면에서 보면 1번 방법은 동일한 연산을 계속 반복하는 반면에 2번 방법의 경우 같은 연산에 대해서는 dp테이블에 기록해둔 값만 참조하면 되기 때문에 보다 빠른 연산이 가능합니다.