# 계단 오르기

# 문제

 

# 입력 및 출력

 

# 풀이

아직도 맞게 푼 건지 잘 모르겠다..

일단 대충 규칙은 생각이 났는데 예외 부분이 너무 많아서 정리만 다섯 번 한 것 같다.

 

1. 맨 마지막엔 1층부터 F층까지 올라야 함 → N-=(F-1)
2. 엘리베이터 타는 횟수를 최소로 만들기 위해 한 번 오를 때 N을 최대로 줄일 수 있는 '1층부터 M층까지 오르기' 반복
     cnt = N/(M-1)
     remain = N%(M-1)
3. 처음 시작 점 즉 F가 1이 아니고 remain이 0이면 cnt++
4. remain 값이 0이 아니면 일단 cnt++, remain 값이 0이 아니고 F+remain > M 이면 cnt++

 

3번 조건이 필요한 이유는 F가 1이 아니면 2번을 반복하기 위해 1층으로 가야하기 때문이다.

여기서 remain값이 0인지 확인하는 이유는 remain 값에 따라 cnt 증가 조건을 따로 세워야 하기 때문에 remain이 0인지 확인해줬다.

위 조건이 필요한 예를 생각해보면 이해가 쉬울 것이다.

10 8 34 이 예를 보면 시작점이 8로 1이 아니고 remain 값이 0이다.

이런 경우엔 시작점인 8층에서 바로 1층으로 이동하는 횟수 1을 증가시켜줘야하기 때문에 cnt값을 1 증가시켜준다.

 

4번 조건이 필요한 이유는 위에서 말한 remain 값에 따른 cnt 증가 조건을 따로 세우기 위해서다.

일단 0이 아니면 처음 F 층에서 계단을 더 오르고 1층으로 내려가야하기 때문에 1층으로 내려가는 엘리베이터 횟수 1을 더해주는 것이고, F층에서 remain만큼 한 번에 계단을 오를 수 있으면 괜찮지만 한 번에 다 오르지 못한다면 엘리베이터를 한 번 더 타야하기 때문에 cnt++를 한 번 더 해준다.

 

#include <fstream>
using namespace std;

ifstream fin("stairs.inp");
ofstream fout("stairs.out");

int main() {
	int t, m, f, n;
	fin >> t;
	while (t--) {
		fin >> m >> f >> n;
		int cnt = 0, remain = 0;
		n -= (f - 1);
		cnt = n / (m - 1);
		remain = n % (m - 1);
		if (!remain&& f != 1) cnt++;
		if (remain) {
			cnt++;
			if (f + remain > m) cnt++;
		}
		fout << cnt << "\n";
	}
}

코드 자체는 간단한데 뭔가 규칙을 찾는게 굉장히 복잡하고 어려웠다.