[백준] 2869번 : 달팽이는 올라가고 싶다- Java(자바)

이번 문제는 달팽이가 하루 동안 올라가고 미끄러지고를 반복하여 원하는 높이의 나무 막대기의 꼭대기에 이르는데까지 걸리는 시간을 구하는 문제였습니다.특이점으로는 낮에는 오르고 밤에는 미끄러지면 정상에 도달한 후에는 미끄러지지 않는다는 점과 시간 제한이 0.15초인 점이었습니다.

Step 0. 해답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Raise_Snail {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int up = Integer.parseInt(st.nextToken());
		int down = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int move = up - down; //실질적인 하루 이동 거리(올라간 거리 - 내려간 거리)
		int safe_m = m - up; //up+down이 무조건 일어나는 날들의 마지노선을 구해줄 때 사용
		if(safe_m == 0) {
			System.out.println(1);
			return;
		}
		int day = safe_m / move;
		 if (day * move + up >= m) {
			System.out.println(day + 1);
		} else{
			System.out.println(day + 2);
		}
			
		
	}
}

문제를 보니 시간 제한의 추가 시간 없음이 보였고 시간이 빡빡한걸로 보아 뭔가 수식을 원하는거 같았지만 우선 for문으로 풀어봤습니다. 역시나 시간 초과가 나왔고 이렇게 시간 초과 때문에 정답 비율이 20프로대였지 않나 싶습니다.

Step 1. 문제 접근

• 달팽이는 하루를 기준으로 낮에는 올라가고 밤에는 미끄러집니다. 또한 정상에 도달하면 미끌어지지 않는다고 적혀있는데 이는 예를 들어 하루에 3미터를 오르고 1미터를 떨어지는데 5미터까지 올라가야한다면 첫 날엔 3미터 -> 3미터 -> 2미터에 위치합니다. 둘째 날에는 2미터 -> 5미터, 즉 정상에 도달하여 더 이상 4미터로는 미끄러지지 않습니다. 이 점을 인지하고 어떤 식으로 풀지 생각했습니다. 생각 결과 하루에 실질적으로 움직이는 거리 (올라간 거리 - 내려간 거리, move 변수)를 구한 후 move(실질적인 이동 거리)가 무조건 실행되는 마지노선의 날을 구한 후 해당 마지노선인 날에 올라간 거리(up)을 더해줬습니다. 여기서 마지노선 날을 구한 이유는 저희가 구하는 마지막 날에 달팽이가 거리를 딱 맞추면 미끄러지지 않지만 그렇지 않으면 미끄러지는 경우가 생기기 때문에 오르고 미끄러지는 경우가 무조건 생기는 날의 마지노선을 구했습니다. 예를 들어 5 ,2 ,17이 입력되었다면 이 달팽이는 하루에 3m씩(5-2) 이동합니다. 하지만 원하는 높이에 도달하는 날에는 5m를 전부 이동하게 됩니다. 그렇기에 우선 3m를 이동하는 날을 구해주고, 원래 이동하는 5m를 이동 시킨 후 더 이동이 가능하다면 그 이틀 후 꼭대기에 도달하게 되는 것이고 5m를 이동 했는데 원하는 높이에 도달 했다면 다음 날에 도달하게 되는 것입니다. 즉 저희가 원하는 day의 전 혹은 전전날을 구하여 원하는 날을 안전하게 구해주었습니다.

Step 2. 문제 풀이

• 우선 이 문제는 시간 제한이 존재합니다. 처음에는 Scanner 클래스를 사용했지만 시간 초과가 떴고 그래서 BufferReader를 사용하였습니다. Scanner와 비교하여 Buffer은 좀 더 오래 되었지만 여러 데이터를 받을 경우 속도가 훨씬 바른 장점을 갖고 있습니다. 단점이라면 String 형태로만 데이터를 받기에 따로 Interger.parseInt등을 사용하여 형태를 변경해주어야 합니다. 또 자체적으로 잘못된 값을 받으면 오류를 발생시키기에 IO오류 처리도 throws시켜줬습니다.

1. 올라간 거리, 미끄러진 거리, 목표 높이를 up, down, m으로 받았습니다.

		int up = Integer.parseInt(st.nextToken());
		int down = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

여기서 시간 제한 때문에 BufferReader를 사용했고 StringTokenizer를 띄어쓰기로 구분하여 받은 후 nextToken으로 불러왔습니다. 이때 String 타입으로 받기 때문에 int형으로 형변환을 시켰습니다.

2. 실질적인 이동 거리(move)와 move가 무조건 일어나는 날들의 마지노선날을 구해주기 위해 필요한 변수(safe_m)를 만들고 이를 이용해 저희가 찾는 최종 날짜를 구하고자 하였습니다.

• safe_m 변수 추가 설명 : 보시면 목표 높이 - 올라가는 이동 거리를 하였습니다. 예를 들어서 보면 4, 2, 21이 입력되었다고 한다면 21 - 4 => 17인것을 알 수 있습니다. 이 17이 의미하는 바는 17미터 까지는 실제 이동 거리(move)가 무조건 발생한다는 것입니다. 즉 4 - 2 인 2미터씩 증가하는게 17미터 전까지는 무조건 발생하므로 safe_m(17) / 2(move) => 16으로 2미터씩 8일을 이동하는건 보장된다는 것입니다. 이후 16미터에 원래 이동하는 4미터를 더해 21미터가 되거나 넘으면 다음날에 도착한 것이고 21미터에 미치지 못 한다면 이틀이 지나고 도착하게 되는 것입니다. 이제 이 내용을 수식으로 해서 나누기를 해준게 3번에서 설명드릴 day 변수 입니다.

		int move = up - down; //실질적인 하루 이동 거리(올라간 거리 - 내려간 거리)
		int safe_m = m - up; //up+down이 무조건 일어나는 날들의 마지노선을 구해줄 때 사용
        if(safe_m == 0) {
			System.out.println(1);
			return;
		}

safe_m == 0은 목표 높이 - 올라가는 높이가 0이 되는, 즉 올라가자마자 목표에 도달하는 경우입니다. 예를 들면 7, 4, 7 같이 첫 날 7미터를 올라가면 바로 목표를 달성하는 경우입니다. 이럴 경우는 바로 1을 프린트 한 후 메서드를 종료하였습니다.

3. day에는 마지노선 날을 구할 때 사용할려고 만들어 둔 safe_m에 실제 이동 거리를 나눠줘서 실제 이동 거리의 마지노선을 구해줍니다.(이 설명은 바로 위 safe_m변수 추가 설명 부분의 내용입니다.) 그 후 day 변수에 + up(높이)를 해줘서(높이를 더해준다는 것은 하루가 지났다는 이야기) 목표 높이에 바로 도달하거나 넘는다면 다음날에 도착을 한 것이고 그렇지 않다면 다음날에 도착하지 못하고 그 다음날에 도착하는 경우가 되겠습니다.

• 마지막에 다음날에 바로 도착하지 못 하는 이유는 위의 예 처럼 4,2,21이라고 한다면 17미터까지가 안전하므로 2미터씩 8일 동안 16미터까지 이동을 하게 됩니다. 여기서 다음 날 4미터를 이동하면 16 + 4 => 20미터이므로 21미터가 안되므로 2미터를 미끄러진 후 19미터에서 4미터를 이동해 21미터에 도착 후 끝나게 됩니다. 즉 마지노선 날의 높이와 실질적인 이동 거리의 결과가 같으면 (예를 들어 2미터씩 이동해서 만약 17미터에 딱 맞았다면 다음날에 21미터에 바로 도착합니다.하지만 현실은 16미터에서 끝맞치게 됩니다.) 다음날에 도착이 가능하지만 아닌 경우도 있기 때문입니다.

		 int day = safe_m / move;
		 if (day * move + up >= m) {
			System.out.println(day + 1);
		} else{
			System.out.println(day + 2);
		}

마지막엔 수식으로 다음날 도착인지 이틀 후 도착인지를 구해줬습니다.

느낀 점

Scanner이외의 입출력 수단도 사용해 보았고 처리 속도라는 관점에서도 문제에 접근해볼 수 있었던 좋은 문제였습니다. 다른 분들은 수식을 한 줄로 끝내는 경우도 있던데 앞으로 더욱 공부를 하여 저도 좀 더 간결한 수식을 만들어내는 능력을 향상시켜야겠다고 생각했습니다.

출처 : 백준 2869번 https://www.acmicpc.net/problem/2869