[ 해결 방법 ]점프를 할 수 있는 범위에서 제일 큰 돌의 좌표를 고르면 된다. 예를 들어 4칸을 뛸 수 있고 현재 위치는 첫번재 돌에 있다. 그리고 돌이 1, 2, 5, 7.. 순으로 있다면, 점프해서 최대로 갈 수 있는 위치는 4이지만 4에 돌이 없으므로 가장 가까운 2로가야한다. 다음엔 2에서 6까지 뛸 수 있지만 6에 돌이 없으므로 가장 가까운 5로간다. [ 코드 ]#include #define INF2000000000int T, tmpT;int pos[1000002];int main(){scanf("%d", &T);tmpT = T;while (tmpT--){int N, K;int pre, cur = 0, next, jmp = 0;scanf("%d", &N);for (int i = 1; i
[ 해결 방법 ]마지막 라운드에서 본인은 최고점을 받고 다른 사람들의 점수보다 크거나 같은지 판단하면된다. 이를 위해서, 우선 입력받은 점수를 오름차순으로 정렬한다. 현재 라운드까지 높은 점수를 받은 사람일 수록 마지막 라운드에서는 낮은 점수를 받아야한다.그래서, 현재 라운드 1등은 1점, 2등은 2점, 3등은 3점처럼 점수를 준다. 현재 라운드에서 자기보다 낮은 점수의 사람은 우승할 가능성이 없다. 자신이 최고의 점수를 받을 것이기 때문이다. 그러니 정렬한 배열에서 현재 인덱스보다 낮은 위치는 고려할 필요가 없다. 문제는 자기보다 높은 점수가 문제이다. 이 중에는 자신보다 높은 점수를 받는 사람이 있을 수 있다.이것을 해결하기 위해서, maxarr이라는 배열을 만들었다. 이 배열은 마지막 라운드 이후에..
https://www.codeground.org/main.do [ 해결방법 ] N이 10만이기 때문에 10만 X 10만의 배열을 선언해서 탐색하면 안된다. 메모리가 넘칠뿐만 아니라 제시간에 탐색할 수도 없다.대신, 좌표로 방번호를 구해야 한다. 좌표점을 가지고 어떻게 방번호를 알 수 있을까? 이 방의 탐색방향은 대각선이다. 예를 들면, (3, 1), (2, 2), (3, 1) 순서대로 탐색한다. 재미있는 것은 탐색방향이 바뀌기 전까지 x + y의 값이 같다는 것이다. 앞의 예에서는 x + y가 4로 모두 같다. 이점을 적극 활용해서 문제를 풀면된다. 우선, 탐색 방향이 바뀌는 점들을 모두 배열에 저장해 놓는다. N이 5일 때, 터닝포인트는 1, 2, 4, 7, 11, 16, 20, 23, 25이다. 다음..