2021-05-08Algorithm5 minutes read (About 686 words) 0 visits

[자바JAVA]백준 2869 달팽이는 올라가고 싶다 풀이

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입출력예시1

//입력
2 1 5

//출력
4

입출력예시2

//입력
5 1 6

//출력
2

처음 시도한 코드

시간초과로 실패

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		int A = Integer.parseInt(input[0]); // 낮에 올라가는 높이
		int B = Integer.parseInt(input[1]); // 밤에 미끄러지는 높이
		int V = Integer.parseInt(input[2]); // 정상 높이

		int oneDay = A - B; // 하루동안 올라갈 수 있는 높이
		int day = 0;
		int sum = 0; // 누적 높이

		while (sum < V) {
			sum += oneDay;
			if (sum == V) {
				break;
			}
			day++;
		}

		System.out.println(day);
	}
}

두번째로 시도한 코드

BufferedReader를 쓴 뒤로 시간초과에 잘 걸리지 않았었는데 당황스러웠다.
그래서 String[]대신 StringTokenizer를, System.out.println()대신 BufferedWriter를 사용해봤다.

시간초과로 실패

하지만 또 시간초과로 실패했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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(), " ");
		int A = Integer.parseInt(st.nextToken()); // 낮에 올라가는 높이
		int B = Integer.parseInt(st.nextToken()); // 밤에 미끄러지는 높이
		int V = Integer.parseInt(st.nextToken()); // 정상 높이

		int oneDay = A - B; // 하루동안 올라갈 수 있는 높이
		int day = 0;
		int sum = 0; // 누적 높이

		while (sum < V) {
			sum += oneDay;
			if (sum == V) {
				break;
			}
			day++;
		}
        bw.write(String.valueOf(day));
		bw.flush();
		bw.close();
	}
}

성공한 코드

런타임을 확실히 줄여 줄 무언가가 필요했다.
시간초과의 원인은 String[]아니고 System.out.println()도 아닌 바로 반복문이었다.
반복문을 제거하고 하니 System.out.println()을 써도 바로 통과되었다.

memory 11500 runtime 76

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int A = Integer.parseInt(st.nextToken()); // 낮에 올라가는 높이
		int B = Integer.parseInt(st.nextToken()); // 밤에 미끄러지는 높이
		int V = Integer.parseInt(st.nextToken()); // 정상 높이
		
		int day = (V - B) / (A - B);
		if((V - B) % (A - B) != 0){
			day++;
		}
		System.out.println(day);
	}
}