인프런 커뮤니티 질문&답변
작성한 질문수
수의 범위와 뽑는개수가 많은경우
해결된 질문
작성
·
309
0
안녕하십니까 선생님, 수들의 조합문제를 풀다가 비슷한 문제를 봐서 풀어보려다가 잘 안되서 질문드립니다. 아래의 문제는 수의 범위가 1000개까지 늘어나있고 뽑는 수는 47개까지 늘어나있습니다. 최악의 경우 경우의 수가 엄청 많아지는데 어떻게 가지를 쳐내야 할지 모르겠습니다.
답변 1
2
김태원
지식공유자
안녕하세요^^
같은 문제라도 입력제한이 커지면 전혀 다른 문제가 됩니다.
이 문제 같은 경우 N값과 K값이 너무 커서 재귀로는 해결할 수 없는 문제입니다. 문제를 보니 다이나믹 문제같습니다.
dy[i][j][m] : i번째까지의 카드 중에서 j장을 뽑아 모든 합을 N으로 나누었을때 나머지가 m인 경우수
로 정의하고 다이나믹하면 됩니다. 배열이 너무 크므로 i값은 0과 1로 토클시키는 방식으로 코드구현을 해야 할 것 같습니다.
최종답은 dy[N][K][0]을 출력합니다.