[C/C++] 백준 #2877 4와 7(수학)

이번 문제는 접근하는 방법을 알고 있으면 쉽게 문제를 풀 수 있습니다.

 

문제의 링크는 다음과 같습니다.

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

 

number generation

 

k번째 작은 숫자라고 했으니까, k+1의 숫자를 2진수로 변환합니다.  예를 들어서 k가 9이라면 k+1은 10이 되며, 이진수로 변환하면, \(1010_2\)가 됩니다.  그러면  처음 1을 제외하고, 1을 7로, 0을 4라 변환하면 됩니다.  결과는 474을 얻게 되겠죠.  4, 7, 44, 47, 74, 77, 444, 447, 474 이므로 우리가 원하는 결과를 얻었음을 알 수 있습니다.

 

왜 k+1을 했는가를 생각한다면, 전 이 문제를 맨 처음은 무조건 1이 있다고 가정했습니다.  이진수 \(1_2\)는 아무것도 없는 상태이고, 이것을 0번째로 작은 수라고 생각하죠.  이진수 \(10_2\)는 첫번째로 작은 수가 되고, 이다음부터는 하나 더 큰 수씩을 하면 됩니다.  \(11_2\), \(100_2\), \(101_2\), ... 형태입니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2877 4 and 7
//        - by Aubrey Choi
//        - created at 2019-08-13
//------------------------------------------------
#include <stdio.h>

//    2, 4, 8, 16
int main()
{
    int n;
    scanf("%d",&n);
    int s=n+1, r[32], i;
    for(i=0; (s>>i)>1;i++) r[i]=((s>>i)&1)*3+4;
    while(--i>=0) putchar(r[i]+'0'); putchar('\n');
    return 0;
}

 

변수 설명

 

• n: 입력된 값입니다. 이 값은 몇 번째 수를 출력할지 결정합니다.

• s: n+1 값을 저장합니다. 이는 비트 시프트 연산을 활용하기 위한 변수입니다.

• r[32]: 결과를 저장할 배열입니다. 여기서 최대 32비트로 결과를 표현할 수 있습니다.

• i: 반복문에서 사용할 인덱스 변수입니다.

 

알고리즘 설명

 

이 프로그램은 4와 7로 이루어진 수열에서 특정 번째 수를 찾기 위해 비트 연산을 사용한 알고리즘을 적용합니다.

 

1. scanf("%d",&n);로 사용자가 입력한 값을 n에 저장합니다.

2. s = n + 1;으로 n보다 1 큰 값을 s에 저장합니다. 이는 계산의 편의성을 위해서입니다.

3. for(i=0; (s>>i)>1; i++) 반복문을 통해 비트 시프트를 사용하여 s의 각 비트를 조사합니다. (s>>i)는 s를 i만큼 오른쪽으로 비트 시프트하여 s의 i번째 비트를 확인합니다.

• ((s>>i)&1)은 s의 i번째 비트가 1인지 0인지를 체크합니다.

• 이 값을 기반으로 *3+4 계산을 하여 r[i]에 7 또는 4를 저장합니다.

• 만약 해당 비트가 1이면 7을, 0이면 4를 의미합니다.

4. 두 번째 while(--i>=0) 루프에서는 배열 r에 저장된 값을 역순으로 출력합니다. 이는 작은 자릿수부터 큰 자릿수 순으로 r 배열에 저장되었기 때문에, 올바른 순서를 출력하기 위해 역순으로 출력하는 것입니다.

5. 마지막으로 putchar('\n');를 호출해 줄 바꿈을 합니다.