[Java] 백준 2869번 문제 '달팽이는 올라가고 싶다'

안녕하세요

'달팽이는 올라가고 싶다'라는 문제를 Java로 풀어봤습니다

이 문제는 제가 아까 포스팅 한 문제에도 설명을 했지만 BufferedReader를 사용해야 하는 문제입니다

왜냐하면 시간이 많이 촉박한 문제이기 때문입니다

 

일단 문제를 보여드리겠습니다

 

https://www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다

문제를 요약해보면

한 달팽이는 높이가 V인 나무 막대를 올라갈 것인데

낯에는 A만큼 올라가지만 밤에는 B만큼 미끄러진다

달팽이가 V에 도착하려면 며칠이 걸리는지 구하는 문제입니다

 

이 문제에서 함정을 찾자면 일단 달팽이가 마지막에 V에 도달하면 더 이상 내려가지 않습니다

이런 함정은 계산식에서 적용해주면 됩니다

고로 그렇게 어렵지는 않습니다

 

하지만 왜 정답 비율이 이렇게 낮은지 보면 시간제한이 다른 문제들보다 타이트합니다

(보통 1~2초입니다)

그래서 저는 처음에 Scanner를 사용해서 문제를 풀었습니다

그랬더니 시간 초과! 라고 뜨면서 문제를 틀렸습니다

 

그래서 저는 BufferReader를 사용했습니다

왜냐하면 Buffer에 문자열을 한 줄씩 읽어드려서 처리하기 때문에 Scanner보다 빠릅니다

그래서 시간제한이 있는 알고리즘 문제는 대부분 BufferReader를 사용합니다

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = 
				new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		
		int A = Integer.parseInt(str.nextToken());
		int B = Integer.parseInt(str.nextToken());
		int V = Integer.parseInt(str.nextToken());
		int day = (V - B)/(A - B);
		
		if((V - B) % (A - B) != 0) day++;
		System.out.println(day);
	}
}

이 문제에서 받은 입력을 띄어쓰기 기준으로 Token을 나누고

integer 값으로 바꾼 다음에 계산 식에 넣습니다

낮(A)에 3만큼 올라가고, 밤(B)에 1만큼 내려간다면 하루에 올라가는 거리는 2입니다

그리고 A-B보다 작은 수의 남는 일 수가 있으면 하루를 더 올라가야 합니다

그래서 V에서 B만큼 빼준 다음에 하루에 올라가는 거리를 나눠주고 나머지가 있으면 1씩 증가시켜주면

달팽이가 목적지에 다온 날짜를 알 수 있습니다

 

여기서 왜 B를 빼주냐고 물으신다면

(대답해드리는 게 인지상정... 죄송합니다... 이제 모르는 사람도 많겠죠??)

정점에 도달하면 내려가지 않는 조건이 있기 때문입니다

 

만약 딱 나누어 떨어지게 올라가면 상관없지만 마지막에 잔여 블록이 생기면

한 번 더 떨어져야 합니다

그 대신 나중에 하루를 더해주는 것이죠

그래서 B를 빼주는 겁니다

 

이 문제는 제한 시간을 짧게 해서 Scanner를 사용하는 것이 아닌 BufferedReader를 사용하는 문제였습니다

다른 코딩 테스트에서도 제한시간이 촉박한 문제들이 나옵니다

그러니 이 문제를 자주 응용해보는 것이 좋을 것 같다고 생각되네요

 

그럼 감사합니다!!!