[for문] 행운의 숫자(lucky number) (1일차)

프로그램 명: luckynum(open)

제한시간: 1 초

4 나 7로 이루어져있는 수를 행운의 숫자라고 한다.

다음은 처음 5개의 행운의 숫자다.

4, 7, 44, 47, 74...

정수 k가 주어졌을 때 k번 째 행운의 숫자를 구하는게 문제다.

입력

정수 k( 1<= k <= 10^9) 가 주어진다.

출력

k번 째 행운의 숫자를 출력한다.

입출력 예

입력

5

출력 

74

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

[문제 풀이]

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

[소스코드 설명]

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

재귀(再歸, Recursion)는 수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 주로 이 방법은 함수에 적용한 재귀 함수(Recursion Function)의 형태로 많이 사용된다. 또, 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다.

- Wiki, 위키백과 -

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

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

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

홀수 : 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;
}