백준 17869번 Simple Collatz Sequence C++ 풀이

 

 

 

곰코딩 블로그 C++ 문제풀이 로고

 

 

설명

입력: 32-bit 부호없는 정수

출력: 정수

입력 받은 수가 짝수이면 나누기 2를
입력받은 수가 홀수이면 1을 더한다.

이 과정을 1이 나올때까지 반복을하고 연산한 횟수를 구한다.

ex) 10을 넣으면
     10은 짝수이기 때문에 2로 나눠서 5,
     5는 홀수이기 때문에 1 더해서 6,
     6은 짝수이기 때문에 2로 나눠서 3,
     3은 홀수이기 때문에 1 더해서 4,
     4는 짝수이기 때문에 2로 나누서 2,
     2는 짝수이기 때문에 2로 나눠서 1
     총 연산 횟수는 6번 결과는 6

 

링크

https://www.acmicpc.net/problem/17869

17869번: Simple Collatz Sequence

 

문제 해설

 

전체적인 코드는 다음과 같습니다.

---

#include <iostream>
#include <string>
#include <vector>

class CSCS
{
private:
	int64_t number = 0;
	int64_t count = -1;
public:
	CSCS();
	~CSCS();
	void userInput();
	int solve();
	void innerSolver(int64_t i);

};

CSCS::CSCS() {
	// constructor
};

CSCS::~CSCS() {
	// destructor
};

void CSCS::userInput() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	
	std::cin >> number;
};

int CSCS::solve() {
	innerSolver(number);
	return count;
};

void CSCS::innerSolver(int64_t i) {
	count++;
	if (i == 1)
	{
		return;
	}

	if (i % 2 == 1)
	{
		innerSolver(i + 1);
		return;
	}
	else
	{
		innerSolver(i / 2);
		return;
	}
}



int main()
{
	CSCS* cSCS = new CSCS();
	cSCS->userInput();
	std::cout << cSCS->solve();
	delete cSCS;
}

위 코드의 핵심인 void innerSolver(int64_t i) 함수를 봅시다.

void CSCS::innerSolver(int64_t i) {
	count++;
	if (i == 1)
	{
		return;
	}

	if (i % 2 == 1)
	{
		innerSolver(i + 1);
		return;
	}
	else
	{
		innerSolver(i / 2);
		return;
	}
}

 

 void innerSolver(int64_t i)는 재귀함수입니다.

 

만일 홀수가 들어오면 1을 더한값으로  void innerSolver(int64_t i)를 호출하고

 

만일 짝수가 들어오면 2를 나눈값으로 void innerSolver(int64_t i)를 호출합니다.

 

함수는 호출될때 마다 cout를 1씩 증가시켜가고 만일 1을 만나면 함수를 종료시킵니다.

정말 간단한 문제이지만 한가지 주의사항이 있습니다.

입력 값이 int32_t범위 이내의 임의의 수라는 것입니다.

 

즉, 만일 int32_t의 최대 값이 들어오면 그 값은 홀수이고

따라서 1을 더하는 과정에서 오버플로우가 발생합니다.

따라서 int32_t나 일반적인 int 사용이 불가능합니다.

 

따라서 int32_t의 최대값이 들어오면 특별한 처리를 해주거나

오버플로우가 발생하지 않도록 int32_t보다 큰 int64_t를 사용하면 해결됩니다.

 

 

 

풀이 코드 링크

https://github.com/dhk1999/coding_problems/blob/main/baekjoon/cpp/problem_17869.cpp

GitHub - dhk1999/coding_problems: 코딩 문제 모음