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

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

 

 

1. 문제 추상화

 

1회에 A만큼 증가한 후 B만큼 감소한다. 몇 회만에 V에 도달할까?

 

2. 제약 조건

 

시간 제한 : 0.15초 

 

3. 알고리즘

 

이전과 이후가 존재하는 문제이다. 그러므로 '반복문'이 적합하다. 그러나 '시간 제한' 있다. 반복문을 사용하면 시간제한에 걸린다. 고로, 연산으로 풀어야 한다. 문제를 풀긴 했지만 인터넷을 찾아보니 더 적합한 풀이법이 있었다. 그러므로 두 가지 풀이법을 소개하려 한다.

 

 

1. 나의 풀이법

 

A = 10, B = 2, V = 100 이라고 가정하자.

 

달팽이는 낮에 10을 갔다가 2를 미끌어진다. 그리고 다시 10을 간다. 낮의 이동을 An이라 하겠다.

 

A1	A2	A3	A4	......
10	18	26	34	.......

 

첫 날 10을 이동한 것을 제외하면 달팽이는 하루동안 8씩 이동한다. 달팽이가 가야하는 길이는 100이다. 첫 날을 제외하면 90이다. 이를 8로 나누면 11.xx이다. 11일을 이동하고 0.xx가 남는다. 그러므로 12일을 이동해야한다. 여기에 첫 날을 추가하면 달팽이는 총 13일을 이동해야 도달한다. 

 

이를 코드로 표현해보자.

 

int distance = V - A; // 첫 날을 제외한 길이
int dif = A - B; // 하루동안 이동하는 거리
int days = (int)Math.ceil((double)distance/dif) + 1; // 달팽이가 이동한 일수

// distance와 dif의 나눗셈의 결과를 Math.ceil() 메소드로 '올림' 한다. 그리고 첫 날을 + 1 한다. 

 

 

나의 풀이는 API를 이용하고 형변환을 한다. API와 형변환을 사용하지 않고 푸는 방법이 있다.

 

 

2. 다른 풀이법

 

달팽이는 낮에 이동하고 밤에 미끌어진다. 그러나 정상에 도달하면 미끌어지지 않는다.

 

고로, 터치다운은 낮에 이루어진다.

( A : 낮동안 이동거리, B : 밤동안 미끌어지는 거리, V : 이동해야하는 거리 )

 

1일 : UP & DOWN ( A - B )

2일 : UP & DOWN ( A - B )

3일 : UP & DOWN ( A - B )

.

.

n-1일 : UP & DOWN ( A - B )

n일 : ONLY UP ( A )

 

이를 식으로 표현하면 이렇다. 

 

( A - B ) ( n - 1 ) + A >= V 

 

n만 좌측에 남기고 모두 우측으로 넘기자.

 

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

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

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

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

 

이를 코드로 표현해보자.

 

int days = ( V - B ) / ( A - B );

 

자료형이 int형이면 '/ 연산'에서 소수점이 제거된다. 그러므로 조건문을 하나 추가한다.

 

if( ( V - B )% (A - B) != 0) {
     days++;
}

 

API나 형변환 없이 단순 연산자만으로 결과가 도출된다. 

 

4. 코드 

 

1. 나의 풀이법

 

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 stz;
		
		stz = new StringTokenizer(br.readLine()," ");
		
		int A = Integer.parseInt(stz.nextToken());
		int B = Integer.parseInt(stz.nextToken());
		int V = Integer.parseInt(stz.nextToken());
		
		int distance = V - A;
		int dif = A - B;
		int days = (int)Math.ceil((double)distance/dif) + 1;
		
		
		bw.write(days+"");
		bw.flush();
		bw.close();
		br.close();
	}
}

 

 

2. 다른 풀이법

 

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 stz;
		
		stz = new StringTokenizer(br.readLine()," ");
		
		int A = Integer.parseInt(stz.nextToken());
		int B = Integer.parseInt(stz.nextToken());
		int V = Integer.parseInt(stz.nextToken());
		
		int days = ( V - B ) / ( A - B );
		
		if( ( V - B )% (A - B) != 0) {
			days++;
		}
	
		bw.write(days+"");
		bw.flush();
		bw.close();
		br.close();
	}

}