doju   4년 전

http://mathworld.wolfram.com/L... 에 따르면 한 번의 encoding에 문자열의 길이가 1.3배 가까이 늘어나므로 이론상 약 30억 글자인 문자열이 주어질 수 있습니다. 그리고 이렇게 되면 당연히 문제를 풀 수가 없습니다.
데이터를 확인하여 입력으로 주어지는 문자열의 최대 길이를 명시하는 것이 좋다고 봅니다.

bupjae   4년 전

개인적인 생각입니다만...

문제 제작자의 의도는 입력 데이터 전체를 메모리에 올려두지 않는 알고리즘을 원하는게 아닌가 싶습니다.


입력 크기가 30억 byte를 넘는 문제들은 이미 많이 있으니까요... (예를 들어 10989번 문제나, 11921번 문제 같은거...)

bupjae   4년 전

... 그런데 풀어놓고 다른 사람 소스 보니 괜히 저 혼자서만 어럽게 푼 것 같네요 :(

bupjae   4년 전

어.으음... 0 개수를 잘못 셌네요 :(

앞에서 쓴 제 발언은 철회하는 걸로 하겠습니다.

doju   4년 전

- 내용 수정해서 다시 적습니다.

저는 그런 풀이가 존재하지 않을 거라고 - 정확히는 어떤 수열이 주어졌을 때 직접 시뮬레이션하지 않고 x번 decoding한 수열의 길이를 구하는 방법조차 없을 것으로 생각합니다. 이 수열은 수학적인 규칙에 의해 재귀적으로 정의된 수열이 아니기 때문입니다.

또한 메모리 문제뿐 아니라 시간상으로도 불가능합니다. 설령 문제가 "주어진 수열의 마지막 숫자를 구하시오" 였어도 일단 30억 글자를 전부 입력받아야 합니다. 참고로 30억 바이트는 3GB 입니다. 예시로 들어 주신 10989번의 경우 데이터를 최대로 만들어도 약 7000만 바이트, 11921번은 약 5000만 바이트입니다.

이 문제는 실제 대회에서 91팀 중 74팀이 해결한, 전체 문제 중 두 번째로 많이 풀린 문제입니다. 저는 대회 측이 그렇게 깊은 뜻을 가졌을 가능성보다는 그냥 시뮬레이션을 의도했고 대회 중에 clarification으로 데이터 제한을 알려 줬을 가능성이 더 크다고 봅니다.

그러고 보니 s의 길이가 항상 pos보다 크다는 조건도 없네요. 이 조건도 추가되어야 할 것 같습니다.

baekjoon   4년 전

추가했습니다.

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