17456번 필살! 60단 컴보
이왜틀!
5년 전이긴 한데 이 문제는 아직도 기억이 생생하다?
당시 이런 고난이도 문제는 익숙하지 않았는데 풀어보겠다고 난리를 피웠다?
제출 현황을 보면 C만 통과해서 Java로는 못푸는 문제인가! 하고 생각 했는데
지금보니 아직도 Java는 한개도 안보인다?
우선 C++로 풀어보고 Java로 포팅해서 되는지 확인한다?
설계
2진수로 바꿔서 세면 그만이긴 한데, 정수 a, b, c의 범위가 2^60 이다.
숫자가 너무 커서 그냥 세면 시간초과가 날 수 밖에 없다.
따라서 적당히 전처리를 해야한다.
순서대로 보자.
1. 테스트케이스 돌리기 전에 최대 60비트까지 가능한 모든 패턴을 계산하는 전처리를 진행한다.
2. c의 점수를 계산한다.
3. 0 ~ b 구간 점수와 0 ~ a - 1 구간 점수의 차를 계산한다.
구현
1. 전처리
0부터 60비트 수까지 가능한 모든 패턴을 계산한다.
테스트케이스도 최대 30만개라서 미리 해놓지 않으면 안된다.
dp[i][j] 는 0 ≤ n < 2^i 중에서 f(n) ≥ j인 개수이며 f(n)은 n의 이진 표현에서 연속된 1 구간들의 길이 제곱 합(실제 점수)이다.
점화식은 dp[i][j] = dp[i - 1][j] + Σ(k = 1 to i) dp[i - k - 1][max(0, j - k^2)]
// 전처리 시작, 가능한 모든 패턴을 미리 계산
ull dp[MAX_BITS + 1][MAX_SCORE + 1];
// dp[i][j] = 0 ≤ n < 2^i 중에서 f(n) ≥ j인 개수, f(n)은 n의 이진 표현에서 연속된 1 구간들의 길이 제곱 합
// 점화식: dp[i][j] = dp[i - 1][j] + Σ(k = 1 to i) dp[i - k - 1][max(0, j - k^2)]
// 점수 0은 0비트에서만 가능하므로 1개
dp[0][0] = 1;
for(int j = 1 ; j <= MAX_SCORE ; ++j) {
// 0비트에서는 0보다 큰 점수가 존재하지 않음
dp[0][j] = 0;
}
// i비트 수까지 확장
for(int i = 1 ; i <= MAX_BITS ; ++i) {
for(int j = 0 ; j <= MAX_SCORE ; ++j) {
// 1. 최상위 비트를 0으로 두는 경우 (0xxx 형태)
// 연속 1구간이 아니므로 i-1 비트로 j 이상 만드는 경우의 수
dp[i][j] = dp[i - 1][j];
// 2. 최상위 비트에서 연속 k개의 1을 쓰는 경우 (110xxx 형태)
// 그 다음 비트가 있다면 0으로 강제, 길이 k의 연속 1 구간이 생성되고, 그 다음부터는 새로운 구간
for(int k = 1 ; k <= i ; ++k) {
// k개의 1 다음에 남는 비트 수
int zero_bit = i - k - 1;
if (zero_bit < 0) {
// k == i일 때 모든 비트가 1
zero_bit = 0;
}
// 앞 연속구간 점수 k^2를 제외하고 남은 필요 점수
int need_score = j - k * k;
if (need_score < 0) {
need_score = 0;
}
// 남은 비트들로 필요 점수 이상 만들 수 있는 경우의 수
dp[i][j] += dp[zero_bit][need_score];
}
}
}
// 전처리 종료
2. c의 점수 구하기
1로 끝나는 경우 남은 점수 추가에 유의한다.
int c_score = 0, len = 0;
// c의 점수 계산 (연속된 1 구간 길이의 제곱 함)
for(int i = 0 ; i < MAX_BITS ; ++i) {
// 1이면 길이증가, 0이면 점수추가
if (c & (1ULL << i)) {
++len;
} else if (len > 0) {
c_score += len * len;
len = 0;
}
}
// 1이 남은 경우 점수 추가
if (len > 0) {
c_score += len * len;
}
3. 구간 점수 차 계산
0부터 특정 구간까지 c의 점수보다 높은 점수를 받은 경우의 수를 찾는 함수를 만든다.
그 다음 0부터 b 구간까지 찾은 수에서 0부터 a-1 구간까지 찾은 수를 빼면 찾는 답이 나온다.
ull find_score(ull dp[MAX_BITS + 1][MAX_SCORE + 1], ull target, int c_score) {
// 60^2를 넘을 경우 예외처리
if (c_score > MAX_SCORE) {
return 0;
}
ull count = 0;
int score = 0, len = 0;
// 최상위 비트부터
for(int i = MAX_BITS - 1 ; i >= 0 ; --i) {
bool bit = (target >> i) & 1;
// 1이면 0으로 바꿔서 더 작은 수 계산
// 0이면 점수추가
if (bit) {
int need_score = c_score - (score + len * len);
if (need_score < 0) {
need_score = 0;
}
// i비트로 필요 점수 이상 만들 수 있는 경우의 수
count += dp[i][need_score];
++len;
} else {
if (len > 0) {
score += len * len;
len = 0;
}
}
}
// 1이 남은 경우 점수 추가
if (len > 0) score += len * len;
// 전달받은 a - 1과 b도 포함
if (score >= c_score) {
++count;
}
return count;
}
// ... 중략 ...
// 0 ~ b 구간 점수와 0 ~ a - 1 구간 점수의 차
ull sector_b = find_score(dp, b, c_score + 1);
// a가 0이면 0 처리
ull sector_a = a == 0 ? 0 : find_score(dp, a - 1, c_score + 1);
cout << (sector_b - sector_a + 1) << "\n";
1차 채점(C++)
C++로는 통과했다.
5년전 나의 원혼을 달래기 위해 이 코드를 그대로 Java로 포팅해서 2차 시도를 해보자.
PyPy로 통과한 이력은 보이는데 Java로는 불가능한 것인가??
2차 채점(Java)
이게되네
흑흑 이거 Java로도 풀 수 있는 문제였어
그냥 옛날의 내가 최적화하지 못한 것 뿐이야
반성
다이나믹 프로그래밍 딱지 붙은 문제는 당분간 피하는게 좋겠다.
뇌가 녹아내릴 것 같다.
코드 확인