백준] 3943 - 헤일스톤 수열(ACM-ICPC Regionals)

시간 제한 : 1초
메모리 제한 : 128MB

 

 

입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 다음 줄부터 T개의 줄에는 헤일스톤 수열의 시작값 n이 주어진다. (1 ≤ n ≤ 100,000)

 

 

출력
각각의 테스트 케이스에 대해서, n으로 시작하는 헤일스톤 수열에서 가장 큰 값을 출력한다.

 

 

소스코드

#include <iostream>
#include <math.h>
using namespace std;
int main(void)
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	int T;

	cin >> T;
	while (T--)
	{
		int n, heils, max;
		cin >> n;
		heils = max = n;
		while (heils!=1)
		{
			if (max < heils)
				max = heils;			
			if (heils % 2 == 0)
				heils /= 2;
			else
				heils = heils * 3 + 1;
		}
		cout << max << '\n';
	}
}

 

Tip

처음에는 문제를 잘못 이해해서 set을 이용해 중복 확인을 하는 불필요한 과정 때문에 시간 초과(TLE)가 났다. 그냥 조건 그대로 문제를 풀면 어렵지 않게 풀 수 있다.