범위때문에 콤비네이션으로 풀다가 포기하는 분들이 있지 않을까 생각을 하면서 제 풀이방법 공유합니다.

콤비네이션으로 풀때 범위가 벗어나는건 DP로 풀때 콤비네이션으로 풀었던 값들을 한곳에 저장할때 발생하지 않을까 라는 생각으로

저는 각 케이스마다 범위를 벗어나지 않게 하기위해  숫자를 나누어 주는 방식으로 풀이했고 정답을 받았습니다.

예시인 13 29를 예를들면

idx = idx * 29 / 1

idx = idx *28 / 2

idx = idx *27 / 3

idx = idx *26 / 4

이런식으로 나아가게 되면 나누기 연산에서 안나누어 지는 수가 발생 할 수 있다고 생각되지만

29 -> 26으로 곱해나가는 수들은 1->4으로 곱해나가는 수들을 최대공약수로 가지기 때문에 문제되지 않습니다.

아직 너무 부족한 코린이지만 혹시 누군가에게 도움이 될 수 있을까 생각되어 글을 써봅니다...