C++로 원하는 페이지에 도달하기 위한 최소 페이지 넘김 횟수 계산하기

문제 개요

N페이지로 구성된 책이 주어졌을 때, 원하는 페이지 K에 도달하기 위해 최소 몇 번의 페이지를 넘겨야 하는지 계산하는 것이 이번 문제의 목표입니다.

• 페이지 넘김은 책의 앞쪽(1페이지부터)에서 시작할 수도 있고, 뒤쪽(N페이지부터)에서 시작할 수도 있습니다.
• 각 페이지는 앞면과 뒷면 두 면으로 이루어져 있지만, 첫 번째 페이지는 뒷면만 존재하며 마지막 페이지 역시 전체 페이지 수에 따라 뒷면만 있을 수 있습니다.

예를 들어 N = 5, K = 4인 경우를 살펴보겠습니다. 이때 필요한 최소 페이지 넘김 횟수는 1회입니다.

• 앞에서부터 넘기는 경우: (1) → (2, 3) → (4, 5) 순서로 총 2번을 넘겨야 합니다.
• 뒤에서부터 넘기는 경우: (4, 5)가 바로 펼쳐지므로 단 1번만 넘기면 됩니다.

따라서 최소 페이지 넘김 횟수는 1입니다.

풀이 알고리즘

아래 공식을 활용하면 최종 결과를 손쉽게 계산할 수 있습니다.

1. K가 짝수인 경우: 앞쪽 거리 = (K − 0) / 2, 뒤쪽 거리 = (N − 1 − K) / 2
2. K가 홀수인 경우: 앞쪽 거리 = (K − 1) / 2, 뒤쪽 거리 = (N − K) / 2

핵심 아이디어는 목표 페이지 K까지 앞쪽에서 접근했을 때의 넘김 횟수와 뒤쪽에서 접근했을 때의 넘김 횟수를 각각 구한 뒤, 두 값 중 더 작은 것을 선택하는 것입니다.

C++ 구현 예제

#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;
}

코드 동작 원리

getMinPageTurns 함수는 먼저 전체 페이지 수 n이 짝수일 경우 n을 1만큼 증가시켜 홀수로 만듭니다. 이는 마지막 페이지가 뒷면만 존재하는 특수한 경우를 일관되게 처리하기 위함입니다. 이후 (k + 1) / 2 식으로 앞쪽 기준 넘김 횟수를, (n − k + 1) / 2 식으로 뒤쪽 기준 넘김 횟수를 계산하고, algorithm 헤더의 min 함수를 사용해 두 값 중 더 작은 값을 반환합니다.

실행 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 출력이 생성됩니다.

Required page turns = 1