Description
문제 조건 : 곱셈, 나눗셈, 수학 함수(math.h)는 사용하지 않는다.
옛날 러시아의 농부들은 구구단(곱셈표)을 몰라도 두 수의 곱을 구할 수 있었습니다. 비밀은 단 세 가지 동작뿐입니다.
- 반으로 나누기 (소수점 아래는 버림)
- 두 배로 불리기
- 더하기
이 방법을 러시아 농부의 곱셈이라고 부릅니다. 방법은 다음과 같아요.
1. 종이에 두 칸(왼쪽·오른쪽)을 만들고, 왼쪽에는 A, 오른쪽에는 B를 적습니다.
2. 왼쪽이 1이 될 때까지 아래 동작을 반복합니다.
- 왼쪽 수를 반으로 나눕니다. (예: 9 ÷ 2 = 4, 소수점은 버려요!)
- 오른쪽 수를 두 배로 불립니다. (예: 5 × 2 = 10)
3. 모든 줄을 살펴보고, 왼쪽 수가 홀수인 줄만 골라서 그 줄의 오른쪽 수를 모두 더합니다.
4. 그 합이 바로 A × B 입니다. 신기하죠?
예시로 이해하기 — 18 × 5
왼쪽(A) 오른쪽(B) 왼쪽이 홀수?
18 5 짝수 → 버림
9 10 홀수 → 더함 (10)
4 20 짝수 → 버림
2 40 짝수 → 버림
1 80 홀수 → 더함 (80)
홀수인 줄의 오른쪽 수만 더하면 10 + 80 = 90, 그리고 실제로 18 × 5 = 90 입니다!
여러분이 할 일은, 두 수 A와 B가 주어질 때 위 방법을 그대로 따라 해서
① 실제로 더해지는 줄(왼쪽이 홀수인 줄)들을 차례대로 출력하고,
② 마지막에 그 합(= A × B)을 출력하는 것입니다.
Input
첫째 줄에 두 정수 A와 B가 공백으로 구분되어 주어진다. (1 ≤ A, B ≤ 1,000)
Output
- 왼쪽 수가 홀수가 되는 줄마다, 그 줄의 왼쪽 수와 오른쪽 수를 공백으로 구분하여 위에서부터 차례대로 한 줄씩 출력한다.
- 마지막 줄에는 그 줄들의 오른쪽 수를 모두 더한 값(= A × B)을 출력한다.
> 왼쪽 수는 마지막에 항상 1이 되고 1은 홀수이므로, 출력은 최소 1줄 이상 + 합계 1줄이 된다.