백준 6615번(콜라츠 추측)[C/C++]

🔗링크

1. 문제 풀이

간단한 문제이다.

주어지는 입력 A,B에 대해 각각
1이 될때까지의 경로를 저장한다.

이후 A경로와 B경로를 역추적하며
각각 경로상의 값이 달라지는 위치을 찾으면 된다.

간단한 예시로 7과 12의 최초 동일 수를 찾으면 다음과 같다.

2. 코드

#include<stdio.h>
#include<vector>
using namespace std;

vector<long long> path[2];

void f(long long n,int s) {
	if (n == 1) {
		path[s].push_back(n);
		return;
	}
	if (n % 2 == 0) f(n / 2,s);
	else f(n * 3 + 1,s);
	path[s].push_back(n);
}

int main() {
	long long A, B, C = 0, i = 0;
	while (1) {
		scanf("%lld %lld", &A, &B);
		if (!A && !B)break;
		path[0].clear();
		path[1].clear();
		f(A, 0);
		f(B, 1);
		i = 0;
		while (1) {
			if (i >= path[0].size() || i >= path[1].size() || path[0][i] != path[1][i]) {
				C = path[0][i - 1];
				break;
			}
			i++;
		}
		printf("%lld needs %lld steps, %lld needs %lld steps, they meet at %lld\n", A, path[0].size() - i, B, path[1].size() - i, C);
	}
	return 0;
}

3. 후기