NotTwo

문제

width x height 크기의 판이 있다.

각 칸에는 1개의 돌을 놓는것이 가능하고,
돌과 돌 사이의 거리는 2가 되어선 안된다.

이 판에 놓을 수 있는 돌의 최대개수를 리턴

width : 1 ~ 1000
height : 1 ~ 1000

예시 입력

1)
3, 2

2)
3, 3

3)
8, 5

예시 출력

4
5
20

생각의 변화

하나의 칸 마다 돌을 놓는 경우, 놓지않는 경우, 2가지 경우가 존재하므로
1000x1000 판인 경우 2^1,000,000 경우가 나올수 있다

탐색보다는, 수식화 하기 좋은 규칙을 찾아서 계산으로 푸는게

이리저리 돌을 놓아보며 생각

왠지 2x2 네모칸이 만들어지는 느낌

짝수행 짝수열에 놓는 최대갯수
+ 짝수행 홀수열에 놓는 최대갯수
+ 홀수행 짝수열에 놓는 최대갯수
+ 홀수행 홀수열에 놓는 최대갯수
= 문제의 답

각 최대갯수들 끼리는 독립적이므로 더할수 있음

따라서 짝수행 짝수열 칸을 따로 모아서 판을 만들면
인접 칸에 돌을 놓지 않는 최대갯수를 구하는 문제로 변경 가능

다시 돌을 놓아보며 수식으로 찾아보려고 했음

시뮬레이션 -> 직관

문득 이런 생각이 듬

짝수행 짝수열 판 칸 갯수 Reven * Ceven
Reven = (height + 1) / 2
Ceven = (width + 1) / 2

인접 칸에 돌을 놓지 않는 최대갯수는 (Reven * Ceven) / 2

짝수행 홀수열 판 칸 갯수 Reven * Codd
Reven = (height + 1) / 2
Codd = (width) / 2

인접 칸에 돌을 놓지 않는 최대갯수는 (Reven * Codd) / 2

같은 흐름으로

홀수행 짝수열 판 칸 갯수 Rodd * Ceven
Rodd = (height) / 2
Ceven = (width + 1) / 2

인접 칸에 돌을 놓지 않는 최대갯수는 (Rodd * Ceven) / 2

홀수행 홀수열 판 칸 갯수 Rodd * Codd
Rodd = (height) / 2
Codd = (width) / 2

인접 칸에 돌을 놓지 않는 최대갯수는 (Rodd * Codd) / 2

최대갯수가 1일때는 예외처리가 필요

최대갯수가 홀수일때도 예외처리가 필요

pseudo code

maxStones(width, height)
    ret = 0
    
    Reven = (height + 1) / 2
    Ceven = (width + 1) / 2
    
    square1 = Reven * Ceven
    
    if (square1 == 1)
        ret += square1
    else if (square2 % 2 == 0)
        ret += (square1 / 2)
    else
        ret += (square1 / 2)
        ret += 1
    
    Codd = (width) / 2
    
    square2 = Reven * Codd
    
    if (sqaure2 == 1)
        ret += square2
    else if (square2 % 2 == 0)
        ret += (square2 / 2)
    else
        ret += (square2 / 2)
        ret += 1
        
    Rodd = (height) / 2
        
    square3 = Rodd * Ceven

    if (square3 == 1)
        ret += square3
    else if (square3 % 2 == 0)
        ret += (square3 / 2)
    else
        ret += (square3 / 2)
        ret += 1
        
    square4 = Rodd * Codd
    
    if (square4 == 1)
        ret += square4
    else if(square4 % 2 == 0)
        ret += (square4 / 2)
    else
        ret += (square4 / 2)
        ret += 1
    
    return ret