알고리즘 수학] 맥너겟수

맥너겟수란?

맥도날드에서 판매하는 치킨 맥너겟은 처음에 6조각,9조각,20조각으로만 판매했는데 이에 6,9,20의 합으로 얻을 수 있는 자연수를 맥너겟 수라고 한다.

예를 들어 6 + 6 = 12, 6+9+9+9+20=53 이므로 12와 53은 맥너겟 수이다.

맥너겟 수에 맥너겟 수를 더하거나 곱해도 맥너겟 수이다.

곧 덧셈과 곱셈은 맥너겟 수의 집합에 대하여 닫혀 있다.

출처 - https://namu.wiki/w/%EB%A7%A5%EB%84%88%EA%B2%9F%20%EC%88%98

맥너겟 수 - 나무위키

위와 같이 맥너겟수가 정의 되어 있는데 여기서 30보다 작은 맥너겟 수는 모두 몇개일까?

문제풀이

위와 같이 먼저 만들 수 있는 6,9,20 위치에 마킹을 한 후 만들 수 있는 수를 만나면 각각마다 6,9,20 을 더해 보면서 만들수 있는 수에 마킹을 하게 되면 된다.

프로그래밍의 동적계획법(Dynamic) 알고리즘이 이와 같이 처리 된다.

정답 : 12개