[지코바] 다른 사람 코드 분석하기 - 달팽이는 올라가고 싶다

1. 문제

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

  자연수 A, B, V가 주어진다. 낮에는 A미터를 올라가고, 밤엔 B미터를 미끄러지는 달팽이가 V미터를 올라가기 위해서는 며칠이 걸리는지 구하는 문제다.

 

2. 코드 분석

코드 원문 링크

[지코바] 6회차 문제풀이

 

코드 전문

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


public class snail {

	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 count = (V-B)/(A-B);
		if((V-B) % (A-B) != 0) {
			count++;
		}
		
		System.out.println(count);
	}
}

 

StringTokenizer

  우선 사용해본 적 없는 클래스인 StringTokenizer가 눈에 들어왔다. 이름 그대로 문자열을 토큰화 하는 클래스인데, 문자열을 어떤 기준에 맞추어 쪼갰을 때 쪼개진 문자열을 토큰이라고 한다.(참고)

public StringTokenizer(String str);											// (1)
public StringTokenizer(String str, String delim);							// (2)
public StringTokenizer(String str, String delim, boolean returnDelims);		// (3)

  생성자는 위에 제시된 세 가지 중 하나를 사용할 수 있다. (1)은 가장 최소한의 형태로, str을 기본 delim으로 나눈다. 여기서 사용되는 기본 delim은 ' (공백문자)', '\t', '\n', '\r', '\f'이다. (2)는 위 코드에서 사용된 형태다. str을 파라미터로 제시된 delim으로 나눈다. 위 코드에서는 ' (공백문자)'를 delim으로 사용했다. (3)은 (2)에서 delim을 토큰으로써 반환할건지 그 여부를 묻는 플래그가 추가된다. 이 플래그가 true일 때 delim 또한 토큰으로써 저장된다. (1), (2)에서는 delim이 제거된다.(참고)

 

알고리즘

  달팽이는 A미터 올라갔다가 자는동안 B미터를 내려간다. 목표 높이 V가 5, 올라갈 수 있는 높이 A가 2, 미끄러지는 높이 B가 1이라 했을 때, 다음과 같이 올라갈 수 있을 것이다.

n번째 날	올라간 높이	미끄러져 도달한 위치
1	2	1
2	3	2
3	4	3
4	5	X

  넷째 날 낮에 목표 높이에 도달했으므로, 밤에 자면서 다시 미끄러질 필요가 없다. 즉, 올라갔다가 미끄러지는 행위(A-B)의 반복(n)은 목표 높이(V)에서 미끄러지는 높이(B)를 한번 뺀 높이에 도달했을 때 멈춰도 된다. 이를 일반화하면 아래와 같은 식을 도출할 수 있다.

( A - B ) * n >= ( V - B )

  그리고 이것을 n에 관한 부등식으로 만들면 아래와 같다.

n >= ( V - B ) / ( A - B )

  운이 좋아 그 동안 올라간 높이와 마지막 날 낮에 올라간 높이의 합이 목표 높이와 일치한다면, n = ( V - B ) / ( A - B ) 의 상황으로 n의 값이 정답이 될 것이다. 그러나 그러지 못한 경우, 달팽이는 부등호 조건에 의해 하루 더 올라가야 한다.