백준/c

백준_2903_중앙이동알고리즘

S0LL 2024. 5. 3. 00:11

 

 

위의 그림과 같은 과정을 n번 거쳤을 때 점의 개수를 구하는 문제입니다.

 

이런 문제는 규칙을 찾아야 하니 규칙이 뭔지 알아보도록 하죠.

  정사각형의 개수 점의 개수
초기 상태 1 4    (2^2)
1번째 4 9    (3^2)
2번째 16 25    (5^2)
3번째 64 81    (9^2)
4번째 256 349    (17^2)
5번째 1024 1089    (33^2)

 

문제에서는 15번째까지 입력받을 수 있지만, 거기까지 구해보는 것은 숫자가 너무 크기도 하고,

이정도까지만 봐도 규칙을 찾을 수 있기에 5번째까지만 구해보겠습니다. 규칙이 보이시니요?

 

우선 정사각형의 개수는 2의 제곱이 계속 곱해지는 것을 확인할 수 있습니다.

이 문제에서는 정사각형의 개수를 구하지 않기 떄문에 크게 상관은 없습니다

(혹여 나중에 정사각형의 개수를 구할 일이 있을 때 떠올리면 될 것 같습니다.)

 

점의 개수를 보면, 모두 n^2 의 형태로 이루어진 것을 확인할 수 있습니다.

 

점의 개수가 늘어나는 규칙을 찾으셨나요?

 

n^2 의 형태에서 n 을 밑이라고 할 때, 

밑이 2의 거듭제곱 만큼 거지는 것을 확인할 수 있습니다.

 

초기 상태 -> 1번째 : 2 -> 3 (+2^0)

1번째 -> 2번째 : 3 -> 5 (+2^1)

2번째 -> 3번째 : 5 -> 9 (+2^2)

3번째 -> 4번째 : 9 -> 17 (+2^3)

4번째 -> 5번째 : 17 -> 33 (+2^4)

 

위의 과정을 보면 규칙을 더욱 쉽게 알 수 있습니다.

 

그럼 이제 코드를 짜볼 차례입니다.

 

 

 

전체 코드

#include <stdio.h>
#include <math.h>

int main(void)
{
    int n;
    scanf("%d", &n);

    int num = 2;
    int dot;
    for (int i = 0; i < n; i++)
    {
        num = num + (int)pow(2, i);
    }
    dot = num * num;

    printf("%d\n", dot);

    return 0;
}

 

코드는 간단합니다.

n을 입력받고, 그만큼 규칙을 적용해주면 끝입니다.

 

규칙을 찾는 재미있는 문제였습니다.

'백준 > c' 카테고리의 다른 글

백준_1436_영화감독숌  (0) 2024.05.03
백준_10989_수정렬하기3(counting sort)  (0) 2024.05.03
백준_1934_최소공배수  (0) 2024.05.01
백준_2751_수정렬하기2_(radixSort)  (2) 2024.05.01
백준_10845_큐(queue)  (0) 2024.05.01