[SWEA] 4301 콩 많이 심기

콩 사이의 길이가 정확하게 2가 되지 않도록 배치를 해야 하는 문제입니다.
거리는 유클리드 거리를 사용하기 때문에 대각선은 고려하지 않습니다.
한번 그려보니 어떻게 풀어야 할지 감이 집혔는데 증명은 못하겠습니다.

총 주기 4를 갖는 형태로
가로 1과 2는 a 값을 갖고 3과 4는 b값을 갖습니다. 주기가 4입니다.
그다음  m을 4로 나눈 값의 갯수 * 2(a*b)를 합니다.
그다음 m을 4로 나누고 나서 나머지에 대해 더해주면 결괏값이 나옵니다.

세로로 보았을 때 4의 주기를 갖습니다.
시간복잡도는 O(1) 입니다.

#include <stdio.h> #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)>(b)?(b):(a)) int test_case, T,n,m,res,a,b; int main(){     setbuf(stdout, NULL);     scanf("%d", &T);     for (test_case = 1; test_case <= T; ++test_case){         res = 0;         scanf("%d%d", &n, &m);         a = n / 4 * 2 + min(n % 4, 2);         b = n / 4 * 2 + max(n -(n/4)*4 - 2, 0);         res += (m / 4) * 2 * (a + b);         m = m - (m / 4) * 4;         if (m) res += a;         if (m>1) res += a;         if (m>2) res += b;         if (m>3) res += b;         printf("#%d %d\n", test_case, res);     }     return 0;  } Colored by Color Scripter

cs