Lucent Blog

저 식을 전개해보면 알 수 있듯이, 이 식은 루트a * 루트b가 정수가 되어야만 식 전체가 정수가 된다.

자, 여기서 잠시 고민해보면, 소인수분해를 사용하면 되리란걸 알 수 있다.

1 ~ N (혹은 M) 을 돌면서 각 숫자들을 소인수분해 한 뒤,

소인수들중에 홀수번 등장하는 인수들을 곱한 수를 L이라 하면,

이제 L에다가 1부터 모든 제곱수(이 수를 S라 하자)를 곱해가며

M보다 작거나 같은 L*S들의 개수를 세면

이 개수가 바로 답이다.

조건을 보면 답은 자연히 0, 1, 2 세 가지 경우밖에 생기지 않는다는 것을 알 수 있다.

0 : 제대로 맞춰져있는 경우

1 : 한 번만 옮기면 되는 경우, 그러니까, 

PP.

PPP

PPP

처럼 되어있는 경우이다.

이런 경우 . (빈 칸)을 포함한 줄을 세로로 한번만 밀면 된다.

2 : 두 번 옮겨야 하는 경우. 예를 들면

P.P

PPP

PPP

처럼 되어있는 경우이다.

이 경우에는 세로로 한 번, 가로로 한 번 옮겨야 한다.

이게 사실... 엄청나게 유명한 문제인걸로 안다

(그래서인지 div2에 나왔음에도 많이 풀린 것 같다).

일단 난 DP를 이용하여 풀었는데,

선끼리 겹치지 않아야 한다는 점에 착안해서 생각해보자.

원 위의 임의의 두 점을 이었다면,

그 점을 기준으로 이 문제는 두 개의 부분 문제로 나눠질 수 있다:

그 두 점보다 위쪽에 있는 점들끼리 이어보는 문제와

그 두 점보다 아래쪽에 있는 점들끼리 이어보는 문제.

이런 식으로 생각해보면,

dp[i][j] = i번째 점 부터 j번째 점 까지 이었을 때, 펭귄 쌍의 최댓값

이라고 정의할 수 있고,

j번째 점과 i <= k < j인 k번째 점을 연결시켰다고 보면,

dp[i][j] = max { dp[i][k-1] + dp[k+1][j-1] + canConnected[k][j] | i <= k < j }

과 같은 점화식을 세울 수 있다.

여기서 canConnected[i][j] 는 i번째 점과 j번째 점이 이어질 수 있는가, 즉,

"i번 펭귄과 j번 펭귄이 좋아하는 색이 같은가?" 이다

(문제의 조건에 따라, 이 때에만 이을 수 이기 때문에).

보자마자 생각났겠지만 이 문제는 다이나믹 프로그래밍을 이용하여 푸는 문제이다.

그런데, 무턱대고 냈다가는 TLE라는 충격적인 결과를 볼 수 있다...!

이걸 넘어가기 위해서는, Leading Zero를 효과적으로 처리해야 한다.

잘 생각해보라.

이 문제를 똑바로 생각했다면..

현재 위치부터 몇 자리의 숫자를 하나로 생각할 것인가? 를 정하는 부분이 있을텐데,

현재 위치부터 아무리 많은 Leading Zero를 하나로 생각하더라도 0이고,

지금 수가 답이 아닌 이상 아무리 많이 선택해도 최적이 될 수 없음은 자명하다.

( e.g. 12340000000000000000000000000000000000000000000000000000000000000000510=61 의 식에서

현재 12,34까지 선택했다고 보자, 그럼 현재 합은 46일텐데, 여기서 0을 선택하나, 00을 선택하나, ...

아무 의미가 없다. 더하기는 하나 추가되었지만 합은 그대로니 최적일 리가 없지 않은가.

최적은 "12+34+000000000000000000..05+10=61"이니까 )

따라서 이런걸 무시하면 엄청난 속도 향상을 이뤄낼 수 있다.

이처럼 사소하지만 중요한 발견을 놓치지 말자.