문제 설명
N 페이지의 책이 주어졌을 때, 과제는 주어진 K 페이지에 도달하기 위한 최소 페이지 회전 수를 계산하는 것입니다.
-
책의 앞면(즉, 1페이지) 또는 뒷면(즉, N페이지)에서 페이지를 넘길 수 있습니다.
-
책의 페이지 수에 따라 뒷면만 있는 첫 페이지와 뒷면만 있는 마지막 페이지를 제외하고 각 페이지는 앞뒷면으로 되어 있습니다.
N =5이고 K =4이면 최소 1페이지를 넘겨야 합니다 -
-
앞에서 페이지 넘김을 시작하면 2턴이 필요합니다 (1) -> (2, 3) -> (4,5)
-
뒤에서 페이지 넘김을 시작하면 (4, 5) 1턴 필요 페이지 넘김 =1
따라서 최소 페이지 수 =1입니다.
알고리즘
최종 결과를 계산하려면 아래 공식을 사용하십시오 -
1. If K is even, front distance = (K – 0)/2 and back distance = (N – 1 – K)/2 2. If K is odd, front distance = (K – 1)/2 and back distance = (N – K)/2
예시
#include <iostream>
#include <algorithm>
using namespace std;
int getMinPageTurns(int n, int k){
if (n % 2 == 0) {
++n;
}
return min((k + 1) / 2, (n -k + 1) / 2);
}
int main(){
int n = 5, k = 4;
cout << "Required page turns = " << getMinPageTurns(n, k) << endl;
return 0;
} 출력
위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -
Required page turns = 1