https://www.acmicpc.net/problem/17167
이 사람 풀이를 보고 있는데
https://measurezero.tistory.com/410
[BOJ 17167 // C ] A Plus Equals B※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※ 이번에 볼 문제는 백준 17167번 문제인 A Plus Equals B이다. 문제는 아래 링크를 확인하자. https://www.acmicpc.net/problem/17167 17167번: A Plus Equals B In the first line, print a single integer $n$ ($0 \le n \le 5\,000$) denoting the number of steps. In the next $n$ lines, print one of the following strings to denote your desired operation: A+=A, A+=B, B+=A, B+=B. Any sequenc..measurezero.tistory.com
0) A=1, B=1, 또는 A=B라면 반복을 종료한다.
1) A와 B가 모두 홀수이면 둘 중 큰 수에 작은 수를 더해준다.
2) A가 홀수이면 A+=A를 한다.
3) B가 홀수이면 B+=B를 한다.
4) A와 B가 모두 짝수이면 두 수를 각각 2로 나누어 저장한다. 이렇게 저장하여도 최종적인 답이 변하지 않는다는 점을 확인하자.
2) 또는 3)의 다음 차례에는 항상 4)가 오므로, 저장된 A와 B의 곱은 두 과정으로 절반이 된다는 점을 확인하자.
또한, 1)을 한다면 다음 차례에는 2) 또는 3)이 이어지므로 저장된 A와 B의 곱이 작아진다는 점을 확인하자. (A=B인 경우는 0번 과정에서 제외되었다는 점과, 작은 수를 큰 수에 더했다는 점을 눈여겨보자.)
따라서 위와 같은 과정을 반복하면 유한번의 연산으로 (저장된 A와 B가) A=1, B=1 또는 A=B인 두 수 A와 B를 얻어낼 수 있다.
저 사람이 뭘하는건지는 이해 했는데
저걸 반복한다고 해서 A=1, B=1 또는 A=B인 두 수 A와 B를 얻어낼 수 있다는 보장이 있음??
저걸 반복하면은 언젠가는 A=1, B=1 또는 A=B가 만들어진다는게 이해가 안가는데
?