BOJ 3007 - 숫자 원
주어진 수열이 $b$이고 원래 수열이 $a$일 때,
$a_{i+3} = a_i + b_{i+2} - b_{i+1}$ 임을 관찰한다.
$3 \nmid n$ 이라면 이 공식을 이용해 모든 칸을 손쉽게 채워줄 수 있다.
$+3$ 씩 인덱스를 올려주는 수열의 $1$번의 순회마다 인덱스가 $1$ or $2$ 칸씩 밀려 원하는 대로 $n$번만에 모두 채워지기 때문
$3 \mid n$이라면 $a_0=x,a_1=y,a_2=z$ 라 하자.
$a_0, a_3, a_6, \dots$ 는 위의 공식을 이용해서 $x$에 대한 상대적인 식으로 구성할 수 있으며 $y,z$ 도 마찬가지다.
항상 정답이 있으므로 채워진 수열 $b$에서 $x$에 대한 상대적인 식 중, 음수가 되지 않도록 최소의 값을 모두 더해준다.
예를 들어 ,$x-7$ 인 곳이 생기면 $8$을 $x$에 대한 상대식에 모두 더해줌이다.
이후에 $\sum_{i=0}^n b_i=S$ 라 할 때, $\dfrac S3=\sum_{i=0}^n a_i$ 이므로 $x,y,z$중 $\dfrac S3$과 차이나는 만큼 값을 증가시켜주자.
$x$라는 값이 $1$증가하면 실제로 $\dfrac n3$씩 증가하는 것이다.
$3 \mid n$은 해가 무수히 많기 때문에 위처럼 찾아줄 수 있다.
Comments