문제
헤일스톤 수열은 다음과 같이 정의 한다.
- n이 짝수라면, 2로 나눈다.
- n이 홀수라면, 3을 곱한 뒤 1을 더한다.
헤일스톤 추측은 임의의 양의 정수 n으로 수열을 시작한다면, 항상 4, 2, 1, 4, 2, 1,...로 끝난다는 추측이다. 이 문제에서는 1이 나오면 수열이 끝난 것으로 처리한다.
n이 주어졌을 때, 이 수열에서 가장 큰 값을 찾아 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 다음 줄부터 T개의 줄에는 헤일스톤 수열의 시작값 n이 주어진다. (1 ≤ n ≤ 100,000)
출력
각각의 테스트 케이스에 대해서, n으로 시작하는 헤일스톤 수열에서 가장 큰 값을 출력한다.
풀이
분류는 다이나믹 프로그래밍으로 되어 있지만 그냥 재귀호출로 풀었다.
아직 다이나믹이 익숙하지 않아서 어떻게 해결해야 될지 감이 안온다.
#include<vector>
#include<iostream>
#include<stdio.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
int heil(int n, int max) {
if (n == 1)
return max;
else if ((n % 2) == 0)
n = n / 2;
else
n = (n * 3) + 1;
if (n > max)
max = n;
return heil(n, max);
}
int main()
{
int t, n;
int *answer;
cin >> t;
answer = new int[t];
for (int i = 0; i < t; i++) {
cin >> n;
answer[i] = heil(n, n);
}
for (int i = 0; i < t; i++)
cout << answer[i] << "\n";
return 0;
}
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[백준 1932번] 정수 삼각형 / C++ (0) | 2020.08.10 |
---|---|
[백준 2163번] 초콜릿 자르기 / C++ (0) | 2020.08.10 |
[백준 1149번] RGB거리 / C++ (0) | 2020.08.08 |
[백준 5052번] 전화번호 목록 / C++ (0) | 2020.08.08 |
[백준 2750번] 수 정렬하기 / C++ (0) | 2020.08.06 |