문제 url:
달팽이는 올라가고 싶다.
문제:
🤔 문제 알아보기
- 이번 문제는 쉽게 풀려면 쉽게 풀 수 있지만, 시간 제한이 있어 까다로운 문제이다.
- 시간 제한이 존재하기 때문에 for문으로 접근하면 안된다.
- for문의 시간복잡도는 O(N)으로 그것보다 더 빠르게 처리될 수 있도록 생각 필요
- 또한 시간 제한만큼 중요한 것이 본문에 정상에 도달하면 더 이상 미끄러지지 않는다.
즉, 정상에 도달하게 되면 -(뺴기)가 되지 않는다는 의미이다. 이 점을 유의해야한다. - 그렇다면 예제를 그림과 함께 살펴보자
먼저 반복문을 이용했을 때 나타낸 코드
2 1 5를 입력하게 되면 총 4일의 시간이 소요되는데, 이를 반복문으로 돌린다면
int day = 1;
int cur_meter = 0;
while(cur_meter < meter) {
cur_meter += up;
if (cur_meter >= meter) {
break;
}
cur_meter -= down;
day++;
}필자는 처음에 이렇게 코드를 생각했으며 현재 위치(cur_meter)가 높이(meter)보다 크면 멈추고 그 전까지 day를 더하는 방식으로 짜보았다.
이렇게 하면 속도가 느려지기 때문에 다른 방법으로 알아보자
위의 그림은 2 1 5를 입력했을 때 나타낸 그림이다.
그림을 봤을 때 하루에 2칸씩 올라간 후 저녁에는 1칸이 줄어 최종적으로 하루에 1칸씩 증가하는 것을 볼 수 있을것이다.
그렇다면!! 굳이 반복문을 쓰지 않고 길이 / (올라간 칸 - 내려간 칸)을 하면 일수를 구할 수 있지 않을까?
그렇다면 5 / (2 - 1)을 하면 총 5일이 된다. 하지만 우리가 원하는 답은 4일이다. 왜 그럴까?
그 이유는 정상에 도달하면 미끄러지지 않는다는 제한이 있기 때문이다.
이 규칙을 어긴 상태로 다시 그림을 그려보겠다.
이렇게 만약 미끄러지지 않는다는 제한이 없었다면, 4일차에 -1을 한 후 다시 정상에 오르기 위해 하루를 더 써야했기에 5일이 된 것이다.
그렇다면 정상에 도달했을 때 미끄러지지 않게 하려면 어떻게 하면 되는 것인가?
간단하게 낮에 올라가서 정상에 도달하면 밤에 내려가지 않도록 설정하면 된다.
(길이 - 내려간 칸)으로 하면 밤에 또 한번 내려가서 다시 하루를 더 올라갈 일을 없앨 수 있는 것이다.
즉 (길이 - 내려간 칸) / (올라간 칸 - 내려간 칸) 을 하면 총 일수를 구할 수 있다.
............... 라고 하면 문제가 이제 틀린다.
그렇다면 왜? 우리는 /를 이용해서 일수를 구한다. 우리가 알아야 할 것은 바로 남아있는 칸의 유무이다.
다음 정리를 다른 블로그에서 발췌한 내용으로 설명해보겠다.
3 1 7
3 1 8
총 두개를 입력받는다고 가정하자. 이를 만약 위의 수식에 넣어 계산하게 되면
(7 - 1 ) / (3 - 1) = 3
(8 - 1 ) / (3 - 1 ) = 3
똑같이 몫이 3으로 나온다. 하지만 3 1 8 같은 경우 3으로 떨어지는게 아닌 3.xx임을 알 수 있는데, 이렇듯 3으로 바로 떨어지지 않고 남은 칸이 존재하면 하루를 더해서 계산해야 하는 것을 볼 수 있다.
그렇다면 이제 코드로 살펴보자.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
// 첫 번째 토큰을 up 변수에 저장
int up = Integer.parseInt(st.nextToken());
// 두 번째 토큰을 down 변수에 저장
int down = Integer.parseInt(st.nextToken());
// 세 번째 토큰을 meter 변수에 저장
int meter = Integer.parseInt(st.nextToken());
br.close();
int day = (meter - down ) / (up - down);
if ((meter -down) % (up -down) != 0) {
day++;
}
bw.write(String.valueOf(day));
bw.close();
}
}
바로 아래 코드가 아까 말했던 로직이다.
if ((meter -down) % (up -down) != 0) {
day++;
}해당 코드는 잔존하는 칸이 존재한다면 하루를 더 올라야 하기에 하루를 더해주는 작업을 수행한다.
