NYPC 2021 예선 | 계단 풀이

[문제]

 

배찌는 1층부터 M층까지 있는 건물의 F층에 살고 있다. 배찌는 이 건물에 있는 계단을 이용해서 운동을 하고 싶다. 배찌는 각 층에서 다음과 같은 일 중 하나를 골라서 하나를 진행한다.

1. 현재 배찌가 있는 곳이 X층이고 X<M이면, 계단을 한 층 올라 X+1층으로 갈 수 있다.
2. 현재 배찌가 있는 위치와 관계없이, 엘리베이터를 타고 원하는 층으로 움직일 수 있다.

배찌는 자기가 살고 있는 F층에서 출발해서, 계단을 한 층 오르는 것을 총 N번 하고 다시 자기가 살고 있는 F층으로 돌아오고 싶어 한다. 그 과정에서 엘리베이터를 타는 것은 언제든 할 수 있다. 운동을 마치기 위해 배찌가 엘리베이터를 타야 하는 횟수의 최솟값을 구하여라.

 

 

[입력 형식]

 

첫 줄에 건물의 총 층수 M, 배찌가 사는 층수 F, 배찌가 오르고 싶은 계단의 총 층수 N이 공백으로 구분되어 주어진다. (2<=M<=1,000,000,000; 1<=F<=M; 1<=N<=1,000,000,000)

 

 

[출력 형식]

 

첫 줄에 배찌가 엘리베이터를 타야 하는 횟수의 최솟값을 출력한다.

 

 

[해설]

 

엘리베이터를 이용해서는 최대 M-1층을 내려갈 수 있으므로, 한 번 엘리베이터를 이용하면 M-1번 계단을 오를 수 있다. F는 관계가 없는데, F층에서 N층으로 올라가서 1층으로 내려간 후 다시 F층으로 돌아가는 것도 총 M-1번 계단을 오른 것이다. 그래서 N/(M-1) 보다 크거나 같은 최소의 정수가 답이다.

 

 

[C/C++ 코드]

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll m,f,n;

int main(){
    cin>>m>>f>>n;
    cout<<(n+m-2)/(m-1);
}

 

조금만 생각해보면 O(1)에 바로 풀리는 문제였습니다 :D