NYPC(Nexon Youth Programming Challenge)는 말 그대로 넥슨에서 주관하는 청소년 프로그래밍 경진대회이다. 참여를 준비하고 있어서, 예선 문제를 풀이하여 보았다.
이 문제의 전문은 다음과 같다:
배찌는 1 층부터 M 층까지 있는 건물의 F 층에 살고 있다. 배찌는 이 건물에 있는 계단을 이용해서 운동을 하고 싶다. 배찌는 각 층에서 다음과 같은 일 중 하나를 골라서 하나를 진행한다.
1. 현재 배찌가 있는 곳이 X 층이고 X < M이면, 계단을 한 층 올라 X+1층으로 갈 수 있다.
2. 현재 배찌가 있는 위치와 관계 없이, 엘리베이터를 타고 원하는 층으로 움직일 수 있다.
배찌는 자기가 살고 있는 F 층에서 출발해서, 계단을 한 층 오르는 것을 총 N 번 하고 다시 자기가 살고 있는 F 층으로 돌아오고 싶어한다. 그 과정에서 엘리베이터를 타는 것은 언제든 할 수 있다. 운동을 마치기 위해 배찌가 엘리베이터를 타야 하는 횟수의 최솟값을 구하여라.
입력은 건물의 총 층 M, 배찌가 현재 사는 층 F, 올라야 하는 계단 수 N이 한 줄로 주어진다.
이러한 느낌의 문제는 대부분은 규칙을 가지고 있다. 코딩 능력이 아닌, 알고리즘 해결 방법을 보는 느낌이 강하게 들었다.
우선, 총 층과 현재 사는 층은 주어진 층을 사용하겠다. 총 층은 10층, 현재 배찌는 8층에 살고 있다고 가정한다.
계단을 하나만 올라야 한다면(N == 1),
- 엘리베이터를 한번 타서, 바로 밑의 층(7층)으로 내려간다.
- 7층에서 8층으로 계단을 타서 올라간다.
로, 엘리베이터를 한번만 타면 된다.
계단을 7칸을 올라야 한다면(N == 7),
- 엘리베이터를 타고, 1층까지 내려간 후
- 8층까지 계단으로 올라온다.
계단을 8칸 올라야 한다면(N == 8),
- 계단을 한칸 올라가고(현재 9층),
- 엘리베이터를 타고 1층으로 내려온다.
- 그 이후 계단으로 8층까지 올라온다.
계단을 10칸 올라야 한다면(N == 10),
- 엘리베이터를 타고 1층으로 내려간다(현재 1층).
- 최고층(10층)까지 쭉 올라간다(오른 계단 9칸, 현재 10층).
- 엘리베이터를 타고 7층으로 내려간다(현재 7층).
- 7층에서 8층으로 계단을 타서 올라간다.
로, 엘리베이터를 타는 횟수가 2회로 늘어난다.
이렇게 엘리베이터 타는 횟수가 늘어나는 곳을 잘 끊어보면,
1 ~ 9회 : 엘리베이터 1번
10 ~ 18회 : 엘리베이터 2번
19 ~ 27회 : 엘리베이터 3번
으로, 9의 배수, 즉 M-1의 배수에서 끊긴다는 사실을 알 수 있다. 올라야 하는 계단의 수(N)를, M-1로 나눈 몫을 올림하면 된다는 것을 위의 예제들을 통해 알 수 있다.
#include <stdio.h>
int main(void) {
int total, floor, stairs;
scanf("%d %d %d", &total, &floor, &stairs);
printf("%d", stairs / (total - 1) + 1);
return 0;
}이 문제의 해설은 다음과 같다:
엘리베이터를 이용해서는 최대 M-1층을 내려갈 수 있으므로, 한 번 엘리베이터를 이용하면 M−1번 계단을 오를 수 있다. F는 관계가 없는데, F층에서 N층으로 올라가서 1층으로 내려간 후 다시 F층으로 돌아가는 것도 총 M-1번 계단을 오른 것이다. 그래서 N / (M-1)보다 크거나 같은 최소의 정수가 답이다.
F가 관계가 없다는 것은 위의 예제로 알 수 있는 사실이었지만, 왜 관계가 없었는지에 대해서는 해설을 보고 확실히 알게 되었다.
