row × col 크기의 행렬 matrix[][]가 주어졌을 때, 다음 조건을 만족하는 셀의 개수를 찾는 것이 이번 문제의 목표입니다.
셀의 값 matrix[i][j] + 해당 셀에 인접한 셀의 개수 = 피보나치 수
참고로 피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … 순으로 이어집니다.
예제로 이해하기
예제 1
입력 — matrix[row][col] = {{1, 4, 1}, {2, 0, 1}, {5, 1, 1}}
출력 — 인접 셀 개수를 더했을 때 피보나치 수가 되는 셀의 개수: 4
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 1 | 4 | 1 |
| 1 | 2 | 0 | 1 |
| 2 | 5 | 1 | 1 |
설명
- Cell(0,0) → 1 + 2 = 3 (인접 셀 2개: (1,0), (0,1))
- Cell(0,2) → 1 + 2 = 3
- Cell(1,0) → 2 + 3 = 5
- Cell(2,2) → 1 + 2 = 3
예제 2
입력 — matrix[row][col] = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}
출력 — 인접 셀 개수를 더했을 때 피보나치 수가 되는 셀의 개수: 9
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 2 | 0 | 0 | 0 |
설명
- Cell(0,0) → 0 + 2 = 2 (인접 셀 2개: (1,0), (0,1)). 마찬가지로 (0,2), (2,2), (2,0)도 동일하게 해당됩니다.
- Cell(0,1) → 0 + 3 = 3 (인접 셀 3개: (0,0), (0,2), (1,1)). 마찬가지로 (1,0), (1,2), (2,1)도 동일하게 해당됩니다.
- Cell(1,1) → 1 + 4 = 5
따라서 9개의 셀 모두 조건을 만족합니다.
프로그램에서 사용된 접근 방식
행렬의 셀은 위치에 따라 단 세 가지 유형으로 나뉩니다. 즉, 모서리(꼭짓점)에 있는 셀은 인접 셀이 2개, 테두리에 있는 셀은 3개, 내부에 있는 셀은 4개입니다. 따라서 각 셀의 값에 2, 3 또는 4를 더한 뒤, check_fibonacci(int num) 함수를 이용해 그 합이 피보나치 수인지 확인하면 됩니다.
- 행렬 matrix[][]를 선언하고 초기화합니다.
- check_square(long double num) 함수는 전달받은 수가 완전제곱수이면 true를 반환합니다.
- check_fibonacci(int num) 함수는 num이 피보나치 수이면 true를 반환합니다.
- check_square(5 * num * num + 4) 또는 check_square(5 * num * num − 4) 중 하나라도 true이면 num은 피보나치 수입니다.
- Fibonacci_cells(int matrix[row][col]) 함수는 인접 셀 개수를 더했을 때 피보나치 수가 되는 셀의 개수를 반환합니다.
- 초기 count 값을 0으로 설정합니다.
- for 루프를 이용해 i = 0 ~ i < row, j = 0 ~ j < col 범위를 순회하며 total = matrix[i][j]로 설정합니다.
- 인접 셀의 개수에 따라 total에 2, 3 또는 4를 더합니다.
- 새로 계산된 total이 피보나치 수라면 check_fibonacci(total)이 true를 반환하므로 count를 1 증가시킵니다.
- 모든 반복이 끝나면 count를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
bool check_square(long double num) {
long double val = sqrt(num);
return ((val - floor(val)) == 0);
}
bool check_fibonacci(int num) {
return check_square(5 * num * num + 4) || check_square(5 * num * num - 4);
}
int Fibonacci_cells(int matrix[row][col]) {
int count = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
int total = matrix[i][j];
if ((i == 0 && j == 0) || (i == row - 1 && j == 0) || (i == 0 && j == col - 1) || (i == row - 1 && j == col - 1)) {
total = total + 2;
} else if (i == 0 || j == 0 || i == row - 1 || j == col - 1) {
total = total + 3;
} else {
total = total + 4;
}
if (check_fibonacci(total)) {
count++;
}
}
}
return count;
}
int main() {
int matrix[row][col] = {{1, 4, 1}, {2, 0, 1}, {5, 1, 1}};
cout << "인접 셀 개수를 더했을 때 피보나치 수가 되는 행렬 내 셀의 개수: " << Fibonacci_cells(matrix);
return 0;
}위 코드를 실행하면 아래와 같은 결과가 출력됩니다.
출력
인접 셀 개수를 더했을 때 피보나치 수가 되는 행렬 내 셀의 개수: 4