한 변의 길이를 나타내는 숫자 size가 입력으로 주어집니다. 목표는 size × size 크기의 체스판 내부에서 만들 수 있는 정사각형 중, 변의 길이가 홀수인 것들의 개수를 구하는 것입니다.
예제로 이해하기
입력
size=3
출력
체스판에서 변의 길이가 홀수인 정사각형의 개수: 10
설명
아래 그림과 같이 모든 정사각형이 표시되며, 여기에는 판 전체를 덮는 3×3 크기의 정사각형 1개도 포함됩니다.
입력
size=4
출력
체스판에서 변의 길이가 홀수인 정사각형의 개수: 20
설명
1×1 크기의 정사각형이 총 16개 있고, 그 안에 3×3 크기의 정사각형이 4개 들어 있습니다. 따라서 16 + 4 = 20개가 됩니다.
접근 방법
이 문제는 변의 길이를 1부터 size까지 순회하면서, 각 홀수 길이마다 해당 길이의 정사각형이 몇 개 존재하는지 세는 방식으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 한 변의 길이가 i인 정사각형은 size × size 격자 안에서 가로 방향으로 (size − i + 1)개, 세로 방향으로 (size − i + 1)개의 위치에 놓일 수 있습니다. 따라서 길이 i인 정사각형의 개수는 (size − i + 1)²개이며, i가 홀수일 때만 이 값을 누적하면 됩니다.
체스판 한 변의 길이를 나타내는 정수 size를 입력받습니다.
함수 square_odd_length(int size)는 size를 받아 변의 길이가 홀수인 정사각형의 개수를 반환합니다.
count 변수를 0으로 초기화합니다.
i를 1부터 size까지 2씩 증가시키며 순회하여 홀수 값만 확인합니다.
각 i에 대해 temp = size − i + 1을 계산합니다.
temp × temp 값을 count에 더합니다.
반복문이 끝나면 count를 결과로 반환합니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
int square_odd_length(int size){
int count = 0;
for (int i = 1; i <= size; i = i + 2){
int temp = size - i + 1;
count = count + (temp * temp);
}
return count;
}
int main(){
int size = 6;
cout<<"체스판에서 변의 길이가 홀수인 정사각형의 개수: "<<square_odd_length(size);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
체스판에서 변의 길이가 홀수인 정사각형의 개수: 56
동작 원리 검증
size = 6인 경우를 살펴보면 다음과 같습니다.
- i = 1 → temp = 6 → 6² = 36개
- i = 3 → temp = 4 → 4² = 16개
- i = 5 → temp = 2 → 2² = 4개
36 + 16 + 4 = 56으로, 실행 결과와 일치합니다. 이 알고리즘은 반복문이 size/2번만 돌기 때문에 시간 복잡도는 O(n)으로 매우 효율적입니다.