[TopCoder] NotTwo(2은 아냐)

Bob은 너비 x 높이의 직사각형 보드를 1 x 1 셀로 나눈다. 보드의 행 번호는 0부터 높이-1까지이고 열 번호는 0부터 너비-1까지입니다.

각 셀은 최대 하나의 스톤을 포함할 수 있으며, 각 스톤 쌍 사이의 유클리드 거리는 2가 아니어야 한다. x1 행의 셀, y1 열과 x2 행의 셀, y2 열 사이의 유클리드 거리는 (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2)로부터의 제곱근으로 정의된다.

그가 칠판에 놓을 수 있는 최대 스톤 수를 반환하십시오.

Definition

Class:

 

NotTwo

Method:

 

maxStones

Parameters:

 

int, int

Returns:

 

int

Method signature:

 

int maxStones(int width, int height)

(be sure your method is public)

Examples

0)

3

2

Returns: 4

He can place four stones on the board. Here is one possible arrangement:

- * *
* * -

1)

3

3

Returns: 5

* - -
* * -
- * *

2)

8

5

Returns: 20

---

 

		X
X		O		X
		X

먼저 문제에 제시된 돌을 놓은 규칙이다. 돌 하나로부터 유클리드 거리 2인 위치에는 돌을 놓을 수 없다.

		X	X
X	X	O	O	X	X
		X	X

 

그렇다면 돌을 하나 더 놓았을 때 그 새로운 돌 주변에도 같은 패턴이 관찰된다.

		X	X
			X
X	X	O	O	X	X
	X		O	X
		X	X
			X

돌을 하나 더 놓아보자.

O	O	X	X	O	O
O	O	X	X	O	O
X	X	O	O	X	X
X	X	O	O	X	X
O	O	X	X	O	O
O	O	X	X	O	O

돌을 계속 놓다보면 위와 같은 패턴이 된다. 물론 규칙을 만족하는 다른 패턴이 있을 수 있지만

 

위의 형태가 가장 단순한 형태의 패턴이 된다. 

 

우리의 일은 height, width의 board가 주어졌을 때 여기에 가장 많이 담을 수 있는 돌의 개수를 구하는 것이다.

 

board 위에 가장 많은 돌을 놓기 위해서는 패턴의 가장 모서리 부분에서 확장해나가야한다.

O	O	X	X	O	O
O	O	X	X	O	O
X	X	O	O	X	X
X	X	O	O	X	X
O	O	X	X	O	O
O	O	X	X	O	O

예를 들어 height가 3, width가 4인 board인 경우 좌측 상단의 모서리부터 뻗어나가면 총 6개의 돌을 담을 수 있다. 

 

우리는 board에 어떻게 해야 돌을 많이 담을 것인가를 고민할 것이 아니라, 이미 패턴이 정해져있으므로 

 

답이 정해져있다. 이 패턴대로 하면 총 몇개가 들어가는가를 구하면 된다. 

 

O	O
O	O

획기적인 발상법이 있다. 

 

나타나는 패턴인 돌 4개를 각각 별개의 돌로 바라보자. 

 

O	O	X	X	O	O
O	O	X	X	O	O
X	X	O	O	X	X
X	X	O	O	X	X
O	O	X	X	O	O
O	O	X	X	O	O

height가 3, width가 4인 예제에서는 빨간 돌이 2개, 파란 돌이 2개, 노란 돌이 1개, 녹색 돌이 1개 담긴다. 

 

그 이유는 모서리부터 뻗어나갔을 때 height가 3, width가 4이므로 빨간 돌, 파란 돌을 2개씩 담을 수 있는 것이고, 

 

노란, 녹색 돌을 1개만 담은 것이다. 

 

이 패턴을 코드로 나타내보자. 

 

using namespace std;

class NotTwo{
    public:
    int maxStones(int width, int height){
        int ans = 0;
        for(int i=0; i<=1; i++){
            for(int j=0; j<=1; j++){
                ans += (((width+i)/2)*((height+j)/2) + 1)/2;
            }
        }
        
        return ans;
    }
};