백준18005🐨Even or Odd?

https://www.acmicpc.net/problem/18005

문제의 주요 조건을 살펴보자.

---

picked n consecutive positive integers between 1 and 10¹⁸ 

guess if their sum is even or odd

If the sum must be even, write 2.
If the sum must be odd, write 1.
If the sum could be even or could be odd, write 0.

The single line of input contains a single integer n (1 ≤ n ≤ 10⁹).

---

 

일련의 $n$개 수의 합이 홀수가 되거나 짝수가 되는 것은
홀수로 시작하는지 짝수로 시작하는지가 영향을 줄 것이다.

홀수로 시작하는 n개의 숫자를 생각해 보면
$(2k+1) + (2k+2) + (2k+i) + ... + (2k+n)$

결국 이 식은 $2 \cdot (k \cdot n)+ \sum_{k=1}^{n} k$ 이 된다.
1에서 n까지의 합을 닫힌 공식으로 나타내면
$n(n+1)//2$이므로, $2(k \cdot n)+ n(n+1)//2$인데
$2(k \cdot n)$는 무조건 짝수이므로 어떤 홀수든지
$1 ~ n$까지의 합이 홀수인지 짝수인지만
확인하면 된다.

짝수로 시작한다면?
$(2k+1+1) + (2k+2+1) + (2k+i+1) + ... + (2k+n+1)$
+1을 n 번 했으니까 
$2 \cdot (k \cdot n) + \sum_{k=1}^{n} k + n$
을 하면 되고
$n(n+1)/2+n$이 홀수인지 짝수인지 확인하면 된다.

결국 

1. $\frac{n(n+1)}{2}$ 가 홀수인가?

2. $\frac{n(n+1)}{2} + n$ 이 홀수인가?

에 따라서

$$
\left\{
\begin{array}{ll}
2, & \text{if the sum must be even} \\
1, & \text{if the sum must be odd} \\
0, & \text{if the sum could be even or could be odd}
\end{array}
\right.
$$

왜 홀수인지 검사하냐면 내가 요즘에 홀짝검사를 할 때 a&1 연산으로 검출하기 때문이다.
만약 a%2==0을 쓴다면 짝수검사 기준으로 생각해야 한다.

 그래서 완성된 첫 번째 코드이다. 이렇게 하면 32ms가 나온다.

n = int(input())
a = (n * (n + 1)) >> 1
b = a + n
#even even 2
#odd odd 1
#even odd 0
print([2,0,1][(a&1)+(b&1)])

좀 더 다듬어 보자. 어차피 a 값이 얼마인지가 중요한 게 아니라 a값이 홀수냐 짝수냐가 중요한 거니까 이렇게 해도 된다.

n = int(input())
a = (n * (n + 1) >> 1)&1
b = (a + n)&1

print([2,0,1][a+b])

이렇게 해도 32ms가 나온다. 32ms의 벽.

그런데 여기서 든 생각이 어차피 a+b의 값은 0 1 2중 하나로 나오는데
리스트 없이 수식의 결과만으로 바로 나오게 할 수 있지 않을까 하는 것이다.

n = int(open(0).read())
a = (n * (n + 1) >> 1)&1
b = (a + n)&1
print(2 - ((a ^ b)<<1) - (a & b))

XOR연산을 이용해서 둘이 다르면 1이 나오니까 *2해서 2에서 빼주면 된다.(a&b는 둘이다르면 무조건 0)
36ms가 나온다.

그런데 이 식도 2- 부분이 마음에 안 들어서 조건을 다시 보다가...
#even even 2
#odd odd 1
#even odd 0

둘이 다르면 값 무시(xor결과를 and연산으로 연결해서)

홀수면 1 짝수면 2니까 ...음? 삼항연산자?

n = int(open(0).read())
a = (n * (n + 1) >> 1)&1
b = (a + n)&1
print(0 if a ^ b else 2-(a&b))

결국 2-는 없앨 수 없었다.

그리고 순위를 확인해보니

나의 최종 1위코드는 

n = int(open(0).read())
a = (n * (n + 1)) >> 1
b = a + n
print([2,0,1][(a&1)+(b&1)])

1등 코드는 어떻게 저렇게 짧게 짰을까?

나는 그것을 열어보고 충격을 받았다......

print([2, 0, 1, 0][int(input())%4])

아놔.....패턴........

덧붙임.

내가 이렇게 제출하면 줏어먹기일까?

더 빠르게 나올까 아니면 32ms의 벽에 막힐까?

print([2, 0, 1, 0][int(open(0).read())%4])

대신 다른 아이디어가 떠올라서 삼항연산자로 다음과 같이 만들었다.

n=int(open(0).read())
print(0 if n&1 else 2-((n>>1)&1))

이건 당당하게 내 아이디어라고 낼 수 있다! 좀 다르잖아. 봐 버렸지만 다른 것을 만들었다.

...에잇 40ms...

https://fal.ai/models/fal-ai/flux/dev

FLUX.1 [dev]모델로 생성한 이미지임.