[동적계획법] 숫자게임

예제) 어떤 퀴즈대회에서 숫자게임이 진행되었다. 숫자게임의 규칙은 주어진 범위 안의 숫자들을 더해 목표하는 수를 만드는 것이다. 중복된 숫자를 사용하는 것은 가능하지만 숫자들의 조합은 두 사람 이상 똑같이 사용할 수 없다. 사용 가능한 숫자 범위와 목표하는 수가 주어졌을 때, 목표하는 수를 만들 수 있는 최대 경우의 수를 구하시오. 

 

숫자 범위 [ 1 , 2 , 3 ]

목표 : 8 

 

 

( 답지에 답은 10이라 나온다. 근데 문제 조건이 너무 헷갈리고 'SSAFY 5일완성' 책이 오류가 상당히 많다. 조건이 애매하니 어떻게 해석하느냐에 따라 결과가 달라진다고 생각한다. 그래서 그냥 내가 해석한 방식대로 풀었고 답은 31은 나왔다. ) 

 

1, 2, 3을 더해 8을 만드는 경우의 수를 구하는 문제이다. 동적계획법의 TopDown 방식으로 접근해보자. 

 

 

 

사용 가능한 문자가 1, 2, 3이니 1, 2, 3을 기준으로 작은 단위로 분류한다. 그리고 각 숫자를 [ 1, 2, 3 ] 으로 만들 수 있는 경우의 수를 배열로 만들어 저장한다. 

 

 

 

 

숫자가 6인 경우는 배열에 존재하지 않는다. 그럼 작은 단위로 분할해서 값을 탐색한다. 

 

 

3은 1가지이다. 4는 3가지이다. 5는 5가지이다. 모두 배열에 저장된 값이므로 작은 단위로 분할할 필요가 없다. 숫자 6이면 경우의 수는 9가지이다. 

 

 

숫자가 7인 경우는 배열에 없으니 작은 단위로 분할해야 한다. 

 

 

4와 5와 6은 배열에 저장되어 있으니 숫자 7인 경우 17가지가 있다. 

 

 

 

그럼 8은 총 31가지가 된다. 

 

 

---

 

참고자료

2021년 7기 모집대비 SSAFY(삼성 청년 SW아카데미) SW적성진단 5일 완성