BOJ 3208 - gus

문제

BOJ 3208 - gus

두 정수 m, n이 주어질 때, 재귀적 방법으로 두 수의 곱을 계산하는 문제이다.

재귀 함수 t(a, b)는 다음과 같이 정의된다:

• a와 b가 모두 0이 아닐 때: t(b, a-1) + 1을 반환
• 그 외 (a 또는 b가 0일 때): -1을 반환

이 함수는 내부적으로 m * n - 1에 해당하는 값을 누적하여 곱셈을 시뮬레이션한다.

입력

• 첫 번째 줄에 두 정수 m, n이 공백으로 구분되어 주어진다.

출력

t(m, n) 함수의 반환값을 출력한다.

예제

풀이

재귀 함수를 통해 덧셈만으로 곱셈을 구현하는 수학적 시뮬레이션 문제이다.

1. 두 정수 m, n을 입력받는다.
2. 재귀 함수 t(a, b)를 호출한다.
3. a 또는 b가 0이면 -1을 반환한다.
4. 그렇지 않으면 t(b, a-1) + 1을 반환하여 b를 a번 더하는 과정을 재귀적으로 수행한다.
5. 최종 결과를 출력한다.

핵심 아이디어: t(a, b)는 실질적으로 a * b - 1을 계산한다. 재귀 호출이 a를 1씩 줄이면서 b를 누적하는 방식으로 곱셈을 덧셈으로 분해한다. 두 수 중 하나라도 0이면 -1을 반환하는 특수 케이스에 주의한다.

코드

#include <iostream>
 
using namespace std;
 
int t(int a, int b)
{
  if (a && b)
    return t(b, a - 1) + 1;
  return -1;
}
int main()
{
  int m, n;
  cin >> m >> n;
  cout << t(m, n);
}

복잡도

• 시간: O(M * N) - 재귀 호출 깊이가 m * n에 비례
• 공간: O(M * N) - 재귀 스택 깊이에 비례