Skip to main content

3021 - Alice and Bob Playing Flower Game

info

풀이 키워드​

스포주의

수학


풀이 코드​

info
  • 메모리: 40670 KB
  • 시간: 0 ms
class Solution {
    public long flowerGame(int n, int m) {
        long ans = 0;
        // odd * even
        ans += (long)(((n+1)>>1)) * (m>>1);
        // even * odd
        ans += (long)((n>>1)) * ((m+1)>>1);

        return ans;
    }
}

풀이 해설​

문제 설명이 부실하다.

문제를 이해하기 쉽게 정리하자면

  • 2줄 있음. 각 줄마다 꽃 x송이 / y송이 심겨있음.
  • Alice 부터 턴 시작
  • 턴마다 x / y줄 중 택1하여 꽃 가져가기
  • 가져갔는데 더이상 꽃이 남아있지 않으면 승리

이 때 꽃은 각 줄마다 [1,n][1,n], [1,m][1,m] 구간에 놓일 수 있다고 할 때,

n과 m이 주어지면 Alice가 이길 수 있는 모든 (x,y)(x,y) 쌍의 개수를 구하는 문제이다.


간단한 수학​

Alice부터 턴을 시작하므로, Alice가 이길 수 있는 경우는 x+y가 홀수일 때이다. 다시 말해,

  • x:홀 / y:짝
  • x:짝 / y:홀

이렇게 2가지 경우로 나뉜다.

// odd * even
ans += (long)(((n+1)>>1)) * (m>>1);
// even * odd
ans += (long)((n>>1)) * ((m+1)>>1);

따라서 코드 상으로는 이렇게 구할 수 있다.

잠재적 실수 포인트

이 문제에서 유도하는 실수 포인트는

  1. 괄호 엄격하게 안해서 산술오류
  2. long 빼먹어서 오버플로우

정도가 있다. 특히 1번의 경우 truncation 때문에 동일 precedence여도 방심하면 안된다.

int n = 4, m = 4;
System.out.println(n/2 * (m+1)/2);
System.out.println((n/2) * ((m+1)/2));
stdout
5
4

메모​

  • 가짜 medium
  • 눈으로만 복습해도 됨