728x90
이 문제를 수학적으로 수열로 해석해서 일반항을 구하고 싶었다.
처음 풀이는 가장 작은 단위의 정사각형 하나를 box라고 하면 모든 box에서 정중앙과 밑변, 오른쪽변 중앙 총 세 개의 점을 찍고, 마지막에 테두리를 돌며 점을 찍으면 된다고 생각했다.
그래서 다음과 같은 수열을 정의하고 코드를 작성했다.
a1=4
a_n+1 = a_n + 4^(n-1) * 3 + 2^(n-1) * 2
a2=4+5=9
a3=9+16=25#include <iostream>
#include <cmath>
int solution(int n) {
if (n == 0) return 0;
int boxes = 1 * std::pow(4, n - 1);
int newDots = boxes * 3 + std::pow(2, n - 1) * 2;
return newDots + solution(n - 1);
}
int main() {
int n;
std::cin >> n;
std::cout << solution(n) + 4;
}
하지만 이는 항과 항 사이의 관계를 귀납적으로 정의한 식이었고
더 간단하게 a_n을 n에 대한 식 하나로 표현하고 싶었다.
그러다 n번 상태의 그림에서 찍히는 점들은 초기 상태의 정사각형에서 가로, 세로 모두 k등분한 후 모든 격자점들을 나타낸 것이라는 것을 보고
k를 구하겠다고 생각했다. 가로 세로 각각 k등분하기 위해 k-1개의 직선을 긋는다고 하면
초기 상태는 k=1, 1번 상태는 k=2, 2번 상태는 k=4이다.
n번 그림에서 n+1번째 그림으로 넘어갈 때 새로 찍히는 직선은 가로, 세로에서 각각 1개, 2개, 4개, 8개.. 라는 것을 찾았고 등비수열의 합을 이용해 n번째 그림에서의 직선 개수를 찾았다.
그리고 가로, 세로에서 각각 그려지는 직선을 n개라고 하면 초기 정사각형 내부에서 만들어지는 점의 개수가 n*n개, 테두리에서 그려지는 점의 개수가 n*4라는 것을 이용해 특정 회차에서 초기에 비해 증가한 점의 수를 출력해주는 solution을 작성했다.
solution의 결과 + 4를 하면 정답이 된다..
/**
b_n = (2^(n-1) - 1) * ((2^(n-1) - 1) + 4)
*/#include <iostream>
#include <cmath>
int solution(int n) {
int lines = std::pow(2, n - 1) - 1;
int res = lines * (lines + 4);
return res;
}
int main() {
int n;
std::cin >> n;
std::cout << solution(n + 1) + 4;
}
728x90
'Programming > C & C++' 카테고리의 다른 글
| [C/C++] C++17 `if` statement with initialization. 유용한 if문 조건 편하게 쓰는 법 (0) | 2024.01.18 |
|---|---|
| [C/C++] 백준 1966번 C/C++ 풀이 (테스트 케이스 제공) (0) | 2023.07.15 |
| Visual Studio 빌드 실패 시 대화창 띄우기 / 숨기기 (0) | 2023.03.23 |
| [C/C++] 백준 1436번 C/C++ 풀이 (0) | 2022.11.10 |
| [C/C++] 백준 1159번 C++ 풀이 (0) | 2022.10.31 |