park780172   9일 전

문제 읽고

백트래킹으로 생각하여

다 구현하고 10 입력하니 244가 나오길래

제출하였더니 시간 초과가 뜨네요.

(시간 초과 예상은 했었으나, 마음만은 아니길 빌었습니다.)

여하튼 중복조합 공식(nHr)과는 답도 다르니,

생각을 계속 해봐도 잘 안 풀리네요.

혹시 힌트라도 주실 수 있으실까요??

seico75   8일 전

지금하신 방법은 n자리에 4개의 숫자를 넣어본다로 접근하신 것 같습니다. 그러면 4^n 이니 1,099,511,627,776 정도 반복인데, 

IXI 나 IIX 나 XII 나 같으니 이것을 생각한다면...

I 가 i1=0~n 번, V 는 i5 = 0~n - i1번, X는 i10 = 0 - i1 - i5 번, L 은 i50 = 0 - i1 - i5 - i10 번 나오는 경우로 생각해볼 수 있을 것 같습니다.

그러면 연산이 (n+1)^4 보다 작아지는 상황이니 194,481 보다 훨씬 작아질 것 같습니다.

결국 4번씩 n 번 재귀하는 것이 아니라 n(보다 작은 숫자)만큼 4번 재귀하는 방법으로 접근하는 것이 좋을 것 같습니다.

park780172   7일 전

답변 감사합니다!!!

해결에 도움이 됐습니다.

댓글을 작성하려면 로그인해야 합니다.