jubin77   2년 전

다이나믹이 뭐예요? 문제 11494번에서

출력부분에 '(1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=109+7)로 나눈 나머지를 출력한다.' 라고 요구조건이 나와있습니다.

그런데 확인한 결과 출력하는 print문 뿐만 아니라

'map[i][j] = map[i-1][j-1]%1000000007+map[i-1][j]%1000000007+map[i][j-1]%1000000007;' 꼴로 다이나믹 점화식을 적어주는 부분에도 mod를 취해야지만 

예시 답안과 같게 나오는것 같습니다.

개인적인 판단으로는 문제 설명에 해당 사항을 추가해주면 좋을것 같습니다.

jcreate98   2년 전

 중간에 더하는 과정에서 세 숫자가 1000000006 이라면 int 범위가 넘어가기 때문에, 저렇게 더하면 안 될 것 같은데, java int 범위가 생각보다 넓은진 모르겠으나 당연히 추가해야 하는 부분 같네요 

wizardrabbit   2년 전

이 문제와 같이 답을 특정 수로 나눈 나머지를 출력하라는 문제는 보통 답이 해당 언어의 정수 자료형에는 담을 수 없을 정도로 매우 크기 때문에 실제로는 매 계산과정이 끝날 때마다 특정 수로 나눈 나머지만 저장하고 있어야 오버플로가 발생하지 않아 올바른 답을 출력할 수 있게 됩니다. Python과 같이 수의 한계가 따로 없는 언어로 모든 과정을 계산한 후, 마지막에 특정 수로 나눈 나머지를 출력하여도 실제 정답과는 일치합니다. 따라서 문제의 서술이 틀린 것은 아닙니다.

또한, 이러한 전략을 알려주는 튜토리얼 문제라면 문제에서 "각 계산을 할 때마다 특정 수로 나눈 나머지를 출력해야 오버플로 및 매우 큰 수 간의 연산으로 시간초과가 나는 문제를 막을 수 있다" 를 언급할 수 있으나, 대부분의 경우 문제를 푸는 사람이 이 정도의 전략은 알고 있을 것이라고 판단하기 때문에, 별도로 언급을 하지 않습니다. 마지막에만 특정 수로 나눈 나머지를 저장하는 방법이 부작용을 일으킬 수 있다는 사실은 문제를 푸는 사람이 직접 생각하여야 한다는 것입니다.

종합하여 말씀드리자면 문제의 답이 매우 크기 때문에 마지막에 한 번만 나눈 나머지를 저장하는 방법은 오버플로를 유발하여 값이 정답과 다를 수 있으며, 매 계산마다 수로 나눈 나머지를 저장하는 전략 역시 문제에서 친절하게 설명해 줄 의무는 없습니다. "이렇게 하면 정수 범위를 벗어나 오버플로가 날 수 있겠구나!" "이렇게 하면 너무 기하급수적으로 수가 커져 시간초과가 날 수도 있겠구나!" -- 모두 문제를 푸실 때 생각해 보셔야 하는 부분이라고 생각합니다 😊

protarie   2년 전

X로 나눈 나머지를 출력한다.

라는 것은 "마지막에만 나머지를 계산하라"라는 뜻이 아닙니다.

코드 전체에 걸쳐서 "X로 나눈 나머지"가 답이 되도록 아이디어를 궁리해야 하는 것입니다.

jubin77   2년 전

다들 친절하신 설명 감사합니다!

전 범위가 벗어나지 않나 싶어서 long, double 등을 사용했으나 같은 값이 나오지 않았기에 해당 글을 작성했으나,

꼭 조건을 문제에 표기하는게 아니라 요구하는 결론을 내기 위한 과정 또한 궁리하는것이 문제에 포함된거군요

앞으로는 내포한 의미를 좀 더 고민해보겠습니다 =)

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