[BOJ] 15918 - 랭퍼든 수열쟁이야!!

문제 출처

[BOJ] 15918 - 랭퍼든 수열쟁이야!!

 

풀이

랭퍼드 수열의 조건을 보면 다음과 같습니다.

 

1. 1 이상 n 이하의 자연수가 각각 두 개씩 들어있다.

2. 두 개의 n 사이에는 정확히 n개의 수가 있다.

 

=> 이 조건은 두 개의 n이 위치한 인덱스는 i, i + n + 1 이라는 것을 말합니다. 그렇기 때문에 문제에서 주어지는 x번째 수와 y번째 수는 y - x - 1 이라는 것을 알 수 있습니다.

 

이 문제는 완전탐색을 통해 풀 수 있습니다. 하지만 그냥 완전탐색을 돌리게 되면 12!이 되어 4억이 넘게 돌아가서 2초를 넘겨 시간초과가 나게 됩니다. 그래서 어떤 조건을 주어 완전탐색을 모두 도는 것이 아니라 일부만 돌아주면 됩니다.

 

1. 숫자는 쌍으로 넣어준다. 현재 인덱스, (현재 인덱스 + 넣을 숫자 + 1)가 비어있는지 확인해서 비어있지 않다면 숫자를 넣어주지 않고 넘어간다.

2. 숫자를 넣을 수 있다면 함수를 다시 호출해 같은 과정 반복

3. x, y 자리에 미리 들어갈 수를 찾아서 고정된 값으로 넣어주지 않으면 시간초과가 난다.

 

코드

small-j/Algorithm