BOJ 2903 - 중앙 이동 알고리즘

출처: https://www.acmicpc.net/problem/2903

---

문제 설명

4개의 점으로 만들어진 사각형에 점을 추가해서 새로운 사각형을 만드는 과정을 진행한다. 점을 추가하는 규칙은 사각형의 중앙과 각 변의 중앙에 추가한다. 이 과정을 N번 시행한후 점의 수를 출력한다.

---

입력

N

출력

N번의 과정이후의 점의 수

---

입력 예

1

출력 예

9

제약조건

1 <= N  <= 15

---

문제 풀이

각 과정에서 늘어나는 사각형의 수, 변의 수, 점의 수들을 단계적으로 계산한다.

- 새로운 사각형은 원래 있던 사각형*4가 된다.

- 새로운 변은 원래 있던 변의 수*2(변의 중점으로 인한 분할) + 사각형*4 (면의 중점과 각변을 연결하는 선)

- 새로운 점은 각 변의 수(새로운 중점)와 사각형의 수(중점) 만큼 추가된다.  

프로그램 내용

...
vector<int> dots(16,0);
vector<int> edges(16, 0);
vector<int> faces(16,0);
    
dots[0] = 4;
faces[0] = 1;
edges[0] = 4;
    
for(int id=1; id<=15 ; ++id)
{
	faces[id] = faces[id-1]*4;
	edges[id] = edges[id-1]*2 + faces[id-1]*4;
	dots[id] = dots[id-1] + faces[id-1] + edges[id-1];
}
...

 

관련된 문제