[백준] 1407번 - 2로 몇 번 나누어질까 (C언어) [Gold4]

input1	output1	input2	output2	input3	output3
176 177	17	5 9	13	25 28	8

해당 문제는 자연수 N이 홀수인 경우와 짝수인 경우로 나누어 생각하면 쉽게 해결가능한 문제이다. 문제 해석 먼저 해보자.

• 홀수 인 경우 f(n) 의 값은 무조건 1이다. 
• 짝수인 경우
  • f(2) = 2, f(4) =4, f(6) = 2 * f(3) ...

문제에서 원하는 수식의 값을 구해보자. S(n) = f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) + f(n) 이다. 점화식으로 표현하면 S(n) = S(b) + S(a-1) 이다.

 

다시 홀수 와 짝수의 경우로 알고리즘을 생각해보면 아래와 같다.

if n % 2 == 0
		f(n/2) = 1 // 짝수를 나누면 홀수
	else
		f(n/2) + 1 = 1

이를 의사 코드로 표현해보자.

.

==> 재귀함수로 표현 가능
	if(n % 2 ==0)
		S(n) = n / 2 + S(n/2)
	else
		S(n) = n / 2 + S(n/2) + 1

전체 소스 코드는 아래와 같다. (범위 제한 때문에 long long int 사용)

#include <stdio.h>
#pragma warning(disable:4996)
long long int func(long long int n) {
	if (n == 0) // 재귀 종료 시점
		return 0;
	else if (n == 1) 
		return 1;
	else if (n % 2 == 0)
		return (n / 2) + 2 * func(n / 2);
	else if (n % 2 == 1)
		return (n / 2) + 2 * func(n / 2) + 1;
}
int main() {
	long long int a, b;

	scanf("%lld%lld", &a, &b);

	long long int result = func(b) - func(a - 1);

	printf("%lld", result);

	return 0;
}

 

[1407번]

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

1407번: 2로 몇 번 나누어질까

 

[github]

https://github.com/MinWook6457

MinWook6457 - Overview