7770 : 아즈텍 피라미드

 

 

계속 에러가 떠서 남들이 어떻게 풀었는지 검색해봤더니, 2x^2+2x+1 이 공식을 사용하여

sum+= 2x^2+2x+1 이런 형태로 풀어냈다.

나는 빡대가리라 그런가 저 공식을 어떻게 구해내는지 머리가 안 돌아가서 그냥 내 방식대로 풀었다.

 

어쨌든 접근법은 맞기에, 그냥 그림 그려가면서 이해를 하고 풀음.

 

<코드>

#include <stdio.h>
int main() {
	int n;
	int x = 1;
	int bottom = 0;
	int sum = 1;
	scanf("%d", &n);
	while (1) {
		sum = sum + (4 * x - 4) + bottom; // 이전의 것 + 밑면의 넓이 겉부분 + 이전 밑면
		if (x == 1)
			bottom = 1;
		bottom += (4 * x - 4);
		//printf("sum : %d, bottom : %d\n", sum, bottom);
		if (sum >= n) {
			if (sum > n)
				x--;
			break;
		}
		x++;
	}
	printf("%d", x);
	return 0;
}

 

높이 - 블록

1    -    1
2    -    6

3  -    19

4  -    44

...

 

초기 밑면은 1로 설정해야하는데 처음부터 bottom=1로 초기화할 경우 sum 계산에 문제가 발생.

그래서 x==1인 경우 bottom=1 이 되도록 설정.(초기 한번만 실행될 수 있도록)

 

sum값과 bottom 값을 업데이트 한 뒤 sum>=n인 경우 루프를 탈출하도록 했다.

sum=n인 경우엔 x를 그대로 출력하면 되지만, sum>n인 경우엔 x-1을 출력하도록 했다.

 

<예시>

루프1. x=1, sum=1, bottom=1

루프2. x=2, sum=1+4+1 = 6

 

ex1) n=5인 경우

sum(6)>n(5)이므로 x=2 -> x=1. break, 1 출력

 

ex) n=6인 경우

sum(6)=n(6)이므로 break. x=2, 2 출력