도전하라! 시작하라!

입력

5

출력 

74

출처: 2010-2011 October COCI Q3
번역+추천: likepad

[문제 풀이]

4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, 747, 774, 777, ....

[소스코드 설명]

이번 문제는 재귀함수를 이용해서 풀어보았습니다.

일단 위에 문제 풀이를 보시면서 규칙이 보이시나요?

만약 제 이전 알고리즘 포스팅을 보신 분이라면 어떤 규칙인지 아실텐데요.

네, 바로 홀수번째와 짝수번째로 나뉘어진 규칙입니다.

홀수 : 4, 44, 74, 444, 474, 744, 774, ...    // 4로 끝나고 있다.

짝수 : 7, 47, 77, 447, 477, 747, 777, ...    // 7로 끝나고 있다.

1의자리가 홀수번째에는 4이고, 짝수번째에는 7로 나타나고 있습니다.

#include <iostream>

using namespace std;
int k;

void recur(int num){
	if(num==0)
		return;
	recur((num-1)/2);
	if(num%2==0)
		cout << "7";
	else
		cout << "4";
}

//4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, 747, 774, 777...
//1의 자리는 4 7반복
//10
int main()
{

	cin >> k;
	
	recur(k);

	return 0;
}

입력

6

출력

1 2 3 6
4
12 

[문제 풀이]

문제는 크게 어려운 부분이 없습니다.

입력한 숫자의 약수와 약수의 갯수와 그 약수들의 곱을 구하는 문제입니다.

[소스코드 설명]

저는 먼저, 약수의 갯수를 세주는 count를 선언해주었습니다.

그리고 입력된 값 n이 for문을 돌면서 나누어 떨어지면 약수가 맞기 때문에 arr 배열에 값을 넣어주고 count값을 증가시켜주는 식으로 했습니다.

#include <iostream>
#include <string>
#define MAX (50)

using namespace std;

int n;

int main(){
	int i, j, k, arr[MAX], count = 0;
	int sum = 0, mul = 1;

	cin >> n;	//6

	//약수 출력 - 1,2,3,6
	for(i=1; i<=n; i++){
		if(n % i == 0){
			arr[count]=i;
			cout << arr[count] << " ";
			++count;
		}
	}
	cout << endl;

	//약수 개수 - 4
	cout << count << endl;;

	//약수 총합 - 12
	//약수 곱의 일의 자리수 - 6
	for(j=0; j<count; j++){
		sum += arr[j];
		mul *= arr[j];
		
	mul = mul%10;
	}

	cout << sum << endl;
	cout << mul << endl;

	return 0;
}

입력

13

출력

0 2 3 

[문제 풀이]

이 문제의 경우 10진수를 2진수로 바꾼 후에 1이 나타나는 위치를 찾는 문제입니다.

주어진 예제에서 13의 경우 2진수로 바꾸면 1101 이 됩니다.

문제에서 제일 오른쪽에서부터 0으로 시작한다 하였으니, 

현재 1이 나타나는 위치는 오른쪽에서부터 순서대로 0, 2, 3이 됩니다.

[소스코드 설명]

저는 짝수일 때와 홀수 일때에 대해서 따로 생각을 했습니다.

홀수 : 0001(1), 0011(3), 0101(5), 0111(7), 1001(9), 1011(11), 1101(13), ...

짝수 : 0010(2), 0100(4), 0110(6), 1000(8), 1010(10), 1100(12), 1110(14), ...

혹시 규칙이 보이시나요?

홀수의 경우 0의 자리가 무조건 1로 끝나고, 짝수의 경우 0의 자리가 무조건 0으로 끝나게 됩니다.

그래서 저는 "isFirst" 라는 것을 선언해서 홀수면서 처음나누어지는 것에 대해서는 무조건 1임을 나타내서 출력할 때 0도 포함이 되게 하였습니다.(1011)

그 다음 10진수를 2진수로 바꾸는 것을 손으로 직접 해보시면 아시겠지만, N값이 1이 될 때까지 계속 나눕니다. 따라서 N이 1이되면 break;로 계산을 멈추게 하였습니다.

그리고 2진수로 바꾸는 것이기 때문에 한 번 계산이 끝날 때마다 N값을 N/2로 갱신해주었습니다.

//bit_pos
#include <iostream>

using namespace std;
int n;

int main(){
	int ans=0;
	bool isFirst = true;

	cin >> n;	//13
	
	do{
		if (n%2 != 0){
			if(isFirst){
				isFirst = false;
			}
			else
				cout << " ";
			cout << ans;
		}
		ans++;
		if(n == 1)
			break;

		n = n/2;

	}while(true);

	cout << endl;
	return 0;
}