isbidip   4년 전

아래 코드로 AC 받았습니다(SPOJ에서도). 우연히, insert 함수 매개변수인 num(새로운 조합으로 만들어지는 수)의 범위를 입력 값인 a의 범위로 한정하였습니다. 초기화 과정에서 5,55,...,55555555까지는 넣어둔 상태지만요.(K가 5일 때)

그런데 이게... , 테스트 데이터가 부족한 건지, 수의 성질 비슷한 그런건지, 아직 반례는 못찾았지만 새로 만들어지는 수를 저렇게 한정할 수 있는 이유가 뭘까요?

코드에 대한 간단한 설명을 하자면....

1. s[i]는 길이가 i인 K 표현 값들의 집합

2. 길이가 n인 K 표현 값들은 다음과 같이 생성합니다. a op b => c (길이가 a인 집합과 b인 집합의 사칙연산 결과를 c인 집합에 삽입)

  1 op 1 => 2

  2 op 1 => 3

  2 op 2 => 4

  3 op 1 => 4

  3 op 2 => 5

  3 op 3 => 6

       ...

  7 op 1 => 8

sait2000   4년 전

문제를 안 풀어서 맞는지는 잘 모르겠는데 아래 경우는 (99999 - 9) / 9 = 11110이니까 답이 7 이하여야 하는 거 맞나요

sait2000   4년 전

그리고 SPOJ와 문제가 조금 다릅니다 SPOJ 쪽에는 나눗셈이 나누어떨어질 때만 가능하다고 써있습니다. 그러니까 다음과 같은 경우는 답이 다를 것 같습니다. (백준의 경우는 9999 / 9 / 9로 만들 수 있습니다) SPOJ 쪽에 이런 데이터가 없나봐요.

그리고 나눗셈의 몫만 취한다는 지문은 나눗셈의 인자가 음수일 때를 어떻게 처리하는지 명확히 제시하고 있지 않습니다. 안 나눠떨어질 때 나눗셈을 해야 하는 데이터가 원래 없으면 번역 실수라 치고 원문처럼 고치면 될 텐데, 어떻게 하면 좋을까요...

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