규칙 찾기 문제. 의외로 까다롭다.
class Solution {
public int solution(int n) {
if (n % 2 == 1)
return 0;
int past = 0, before = 1;
long answer = 1;
n >>= 1;
for (int i = 0; i < n; i++) {
past = before;
before = (int)answer;
answer = (4 * answer - past) % 1000000007;
}
return (int)answer + (answer >= 0 ? 0 : 1000000007);
}
}
if (n % 2 == 1)
return 0;
짝수가 아니라면 0 반환. 홀수라면 공간을 채울 수 없다.
int past = 0, before = 1;
long answer = 1;
n >>= 1;
2차례 전의 값 past, 1차례 전의 값 before, 현재값 answer 선언. answer는 값 변환 이슈가 있어 long으로 선언했다.
n을 2로 나눠(비트 n번 이동 == 2^n으로 나눔) 계산의 편의를 더했다.
for (int i = 0; i < n; i++) {
past = before;
before = (int)answer;
answer = (4 * answer - past) % 1000000007;
}
해당 식을 이해하기 위해선 먼저 규칙을 찾아야 한다.
먼저 n에 2칸이 주어졌다고 생각하자. 경우의 수는 3이다. 생각하기 쉽게 f(2) = 3
으로 두자. 이는 특정 칸이 주어졌을 때, 만들 수 있는 경우의 수
라고 하자.
4가 주어진다면, 앞선 경우의 수(f(2)
) * 나머지 2칸의 경우의 수(3) + 4칸으로 만들 수 있는 특이 케이스(2)로 정의할 수 있다.
특이 케이스란 예제에서 확인할 수 있는 이 2가지인데, 이는 n이 몇이든 무조건 2가지만 생성된다.
정리하자면, f(4) = 3f(2) + 2
이다.
6칸은 앞선 경우의 수(f(4)
) 나머지 2칸의 경우의 수(3) + 2칸 먼저 차지(f(2)
) 4칸의 특이 케이스(2) + 6칸의 특이 케이스(2) => f(6) = 3f(4) + 2f(2) + 2
이다.
8칸도 마찬가지로 f(8) = 3f(6) + 2f(4) + 2f(2) + 2
로 표현할 수 있다.
한 번에 정리해보겠다.
f(2) = 3
f(4) = 3f(2) + 2
f(6) = 3f(4) + 2f(2) + 2
f(8) = 3f(6) + 2f(4) + 2f(2) + 2
f(10) = 3f(8) + 2f(6) + 2f(4) + 2f(2) + 2
...
f(2n) = 3f(2n - 2) + 2f(2n - 4) + ... + 2f(2n - 2k) + 2
이 때, f(8)
과 f(6)
을 자세히 보자.
f(8) = 3f(6) + 2f(4) + 2f(2) + 2
에서 2f(4) + 2f(2) + 2
의 형태가 꼭 f(6) = 3f(4) + 2f(2) + 2
과 닮지 않았는가?
f(6)
에서 f(4)
를 뺀 값과 같다!
즉, f(8)
을 다시 정의하자면 f(8)
= 3f(6) + 2f(4) + 2f(2) + 2
= 3f(6) + f(6) - f(4)
= 4f(6) - f(4)
로 표현할 수 있다.
따라서 식을 다시 정리하자면
f(-2) = 1 (식의 규칙을 맞추기 위한 초기값)
f(0) = 1 (식의 규칙을 맞추기 위한 초기값)
f(2) = 4f(0) - f(-2)
f(4) = 4f(2) - f(0)
f(6) = 4f(4) - f(2)
f(8) = 4f(6) - f(4)
f(10) = 4f(8) - f(6)
...
f(2n) = 4f(2n - 2) - f(2n - 4)
로 더 쉽게 표현할 수 있다.
위에서 정의한 변수로 표현한다면 answer = (4 * before - past)
가 될 것이다.
그러나, before의 최대값은 1000000007의 나머지이니 1000000006이 된다.
4로 곱하면 int의 범위를 넘어버려 overflow가 일어난다.
따라서 long인 answer로 수식을 완성하고, 1000000007로 나눠주자.
return (int)answer + (answer >= 0 ? 0 : 1000000007);
past가 1000000007에 가까운 값이고, before이 0에 가까운 값이었다면 answer은 음수가 나올 수 있다. 음수일 때는 1000000007을 더해 본래 표현될 값을 찾게끔 하자.
def solution(n):
if n % 2:
return 0
answer = 0
for i in range(n // 2 + 1):
one = n - (2 * i)
two = i
min_cnt = min(one, two)
A = B = 1
for j in range(min_cnt):
A *= n - i - j
B *= j + 1
answer += A // B * (2 ** (one // 2))
return answer % 1000000007
대체 과거의 나는 무슨 규칙을 찾았었길래 이런 식을 도출했을까..?
그리고 왜 맞는걸까..?
나중에 해석하게 되면 작성하기로..
해야 할 것들이 넘쳐나서 시간 분배가 중요하게 되었다. 평소 같았으면 Python 풀이도 해석좀 해보겠는데.. 대체 뭐 어떻게 푼거지?
일단 Java 풀이가 Python보다는 더 나아보인다.