중간에 더하는 과정에서 세 숫자가 1000000006 이라면 int 범위가 넘어가기 때문에, 저렇게 더하면 안 될 것 같은데, java int 범위가 생각보다 넓은진 모르겠으나 당연히 추가해야 하는 부분 같네요
14494번 - 다이나믹이 뭐예요?
이 문제와 같이 답을 특정 수로 나눈 나머지를 출력하라는 문제는 보통 답이 해당 언어의 정수 자료형에는 담을 수 없을 정도로 매우 크기 때문에 실제로는 매 계산과정이 끝날 때마다 특정 수로 나눈 나머지만 저장하고 있어야 오버플로가 발생하지 않아 올바른 답을 출력할 수 있게 됩니다. Python과 같이 수의 한계가 따로 없는 언어로 모든 과정을 계산한 후, 마지막에 특정 수로 나눈 나머지를 출력하여도 실제 정답과는 일치합니다. 따라서 문제의 서술이 틀린 것은 아닙니다.
또한, 이러한 전략을 알려주는 튜토리얼 문제라면 문제에서 "각 계산을 할 때마다 특정 수로 나눈 나머지를 출력해야 오버플로 및 매우 큰 수 간의 연산으로 시간초과가 나는 문제를 막을 수 있다" 를 언급할 수 있으나, 대부분의 경우 문제를 푸는 사람이 이 정도의 전략은 알고 있을 것이라고 판단하기 때문에, 별도로 언급을 하지 않습니다. 마지막에만 특정 수로 나눈 나머지를 저장하는 방법이 부작용을 일으킬 수 있다는 사실은 문제를 푸는 사람이 직접 생각하여야 한다는 것입니다.
종합하여 말씀드리자면 문제의 답이 매우 크기 때문에 마지막에 한 번만 나눈 나머지를 저장하는 방법은 오버플로를 유발하여 값이 정답과 다를 수 있으며, 매 계산마다 수로 나눈 나머지를 저장하는 전략 역시 문제에서 친절하게 설명해 줄 의무는 없습니다. "이렇게 하면 정수 범위를 벗어나 오버플로가 날 수 있겠구나!" "이렇게 하면 너무 기하급수적으로 수가 커져 시간초과가 날 수도 있겠구나!" -- 모두 문제를 푸실 때 생각해 보셔야 하는 부분이라고 생각합니다 😊
댓글을 작성하려면 로그인해야 합니다.
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를 취해야지만
예시 답안과 같게 나오는것 같습니다.
개인적인 판단으로는 문제 설명에 해당 사항을 추가해주면 좋을것 같습니다.