위의 그림과 같은 과정을 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 |