정답
① return n, ② robot(n - 1) + robot(n - 2) + robot(n - 3), 거리 6 입력 시 출력 값은 24, 37 입력 시 출력이 음수가 되는 이유는 32비트 정수형 int의 범위를 넘는 정수 오버플로가 발생하여 최상위 비트가 부호 비트로 1이 되어 음수로 해석되기 때문이다.
출제 의도
1, 2, 3미터씩 이동할 수 있는 로봇이 n미터를 이동하는 모든 방법의 수를 점화식으로 나타내고, 이를 재귀 함수로 구현하는 능력을 평가한다. 또한 C 언어의 32비트 정수형 범위를 이해하고, 큰 수 계산에서 오버플로가 발생하면 부호가 바뀌어 음수 결과가 나올 수 있음을 이해하는지를 묻는다.
풀이 과정
로봇이 한 걸음에 1m, 2m, 3m를 갈 수 있을 때, n미터를 이동하는 방법의 수를 \(robot(n)\)이라고 하자.
문제에서 작은 값에 대한 값이 이미 주어져 있다.
\[ robot(1) = 1,\quad robot(2) = 2,\quad robot(3) = 4 \]
이제 \(n > 3\)인 경우를 생각한다. 첫 걸음을 1m, 2m, 3m 중 어디로 가느냐에 따라 경우가 나뉜다.
- 첫 걸음을 1m 가면 남은 거리 \(n-1\)m를 가는 방법 수는 \(robot(n-1)\)
- 첫 걸음을 2m 가면 남은 거리 \(n-2\)m를 가는 방법 수는 \(robot(n-2)\)
- 첫 걸음을 3m 가면 남은 거리 \(n-3\)m를 가는 방법 수는 \(robot(n-3)\)
서로 겹치지 않는 경우들이므로, 전체 경우의 수는 세 경우를 모두 더한 값이 된다.
\[ robot(n) = robot(n-1) + robot(n-2) + robot(n-3)\quad (n \ge 4) \]
따라서 C 함수 robot는 다음과 같이 작성해야 한다.
① 부분은 \(n = 1\)일 때 1, \(n = 2\)일 때 2를 돌려주어야 하므로, 입력된 값을 그대로 반환하면 된다.
\[ n = 1 \text{ 또는 } n = 2 \Rightarrow robot(n) = n \]
따라서
if (n == 1 || n == 2) return n;
가 ①에 들어간다.
② 부분에는 위에서 구한 점화식을 그대로 코드로 옮기면 된다.
\[ robot(n) = robot(n-1) + robot(n-2) + robot(n-3) \]
이므로
return robot(n - 1) + robot(n - 2) + robot(n - 3);
가 ②에 들어가야 한다.
이제 이 함수로 거리 6을 계산해 보자. 점화식을 이용해 차례로 값을 구하면,
\[ \begin{aligned} robot(1) &= 1,\\ robot(2) &= 2,\\ robot(3) &= 4,\\ robot(4) &= robot(3)+robot(2)+robot(1)=4+2+1=7,\\ robot(5) &= robot(4)+robot(3)+robot(2)=7+4+2=13,\\ robot(6) &= robot(5)+robot(4)+robot(3)=13+7+4=24. \end{aligned} \]
따라서 프로그램 실행 시 6을 입력하면 출력값은 24가 된다.
다음으로, 36과 37을 입력했을 때의 결과를 보자. 문제에서 주어진 결과는 다음과 같다.
\[ \text{입력 } 36 \Rightarrow 2082876103,\quad \text{입력 } 37 \Rightarrow -463960867 \]
C 언어에서 int는 보통 32비트 정수형이며, 표현 가능한 범위는
\[ -2^{31} \le x \le 2^{31} – 1 \]
즉,
\[ -2147483648 \le x \le 2147483647 \]
이다. \(robot(36)\), \(robot(37)\)은 매우 큰 수가 되는데, \(robot(37)\)을 계산하는 과정에서
\[ robot(37) = robot(36) + robot(35) + robot(34) \]
의 값이 이 범위를 넘어가게 된다. 32비트 정수에서 범위를 넘으면 상위 비트가 잘려 나가면서 값이 모듈로 \(2^{32}\) (또는 부호를 고려하면 \(2^{31}\))로 계산되는 오버플로가 발생한다.
이때 최상위 비트(부호 비트)가 1이 되면, 그 값은 음수로 해석된다. 따라서 실제 수학적인 \(robot(37)\) 값은 양수이지만, 32비트 int 형에서 오버플로가 났기 때문에 메모리에 저장된 이진수가 음수 범위에 해당하게 되어, 출력 결과가 -463960867과 같은 음수로 나타나는 것이다.
결론적으로 37을 입력했을 때 출력이 음수가 되는 이유는, 재귀적으로 더해지는 값이 너무 커서 32비트 int 형의 최대값을 넘는 정수 오버플로가 발생하고, 그 결과 부호 비트가 1이 되어 음수로 해석되기 때문이다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>