https://www.acmicpc.net/problem/24916
문제요약
- 서로 다른 숫자, 증가하는 수열(N : 10만, 숫자 : -10^6 ~ 10^6)
- 특정 위치에서 시작해서 점프. x를 점프했으면 다음번에는 2x 점프
- 모든 점을 밟을 수 있는지/없는지
- 테스트케이스 : 50000개, 전체 N의 합 : 100만개
접근법
- N이 작으면 어떻게 가능할 것 같다..
- 2배씩 증가한다면, 1, 2, 4, 8, ...
- 숫자의 최대 크기는? : 10^6 = 2^20
- -10^6 에서 10^6으로 점프한다하면 2^21
- N이 엄청 커지면 숫자 범위를 넘어가서 안될 것 같다!
- 가장 큰 N을 찾아보면
- -10^6, +1, +2, .... 를 해보면 21개 => 처음에는 21개가 최대인줄 알았는데 아니었음
- 0, -1, 1, 3, -5 ==> 22개
- 22개보다 큰 수열은 모두 밟을 수 없다!
- 1개만 주어지면 모두 밟을 수 있다!
- N <= 22인 경우에 대해 생각해보면
- 안쪽부터 밟아나가야함
- 가까운 곳을 건너뛰어서 밟더라도 결국은 안쪽을 밟아야하는데
- 어디로 가든 더 많은 점프를 해야하므로 불리함을 알 수 있다
- dp[a][b] 처럼 표현이 가능
- dp에 값을 넣어서 그 값보다 작냐 크냐로 판단하는 접근법
- a ~ b 사이는 다 밟은 상태에서 a위치에 있는 상태
- a < b인 경우
- 왼쪽으로 가거나 => [a - 1][b]
- 오른쪽으로 가거나 => [b][a - 1]
- a > b인 경우도 유사하게 가능
- dp[a][b] : a ~ b 이후를 클리어하기 위해 가능한 최대 값 : 최대값을 갖는 이유는 2배씩 뛰는 제약조건때문에 진행한 값이 클 수록 불리하고, 가장 클 수 있는 값이 존재하기 때문이다. 즉 진행했을때 dp[a][b]보다 작은 값으로 점프해왔으면 이후 클리어가 가능 할 것임
- 그 다음 처리
- 특정 위치에서 두 방법으로 점프를 할 수 있고, 간격과 비교해서(간격 x 2 이상인지) 가능한 경우 중에 큰 값이 이 구간에서의 최대 한도임
- 시작점이 2인 경우 (2,3), (2,1)중에 가능한 것이 있는지 판단하는 식으로 진행함
- 예외 처리
- dp[1][n] : 가장 끝이고, 한쪽으로 점프하면 되므로 n->1 간격이하로 진입하면 됨
- dp[k][0] : (1, k)에 있을때, 1 -> k로만 가능. 즉 1을 밟고 왔기때문에 0이 됨. 이후 가능한 방법은 (k+1, 0), (k+2, 0), ...
- dp[n][0] : 이 경우는 임의의 큰 값 (2^22)으로 함. 어떤 점프로 와도 다 가능하도록. 이때 2^21이 충분히 클 줄 알았는데 아님. 2^20보다 큰 값으로 와서 걸리는 경우가 있는 것 같음
후기
- 적당히 큰 값에서 안전하게 더 큰 값을 사용해도 좋겠다.
- 2^21은 왜 안될까??
newbieski