[BJ] 2869 - 달팽이는 올라가고 싶다

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

오늘은 백준의 2869번 문제인 달팽이는 올라가고 싶다에 대해 알아보도록 하겠습니다.

 

 

접근 방법

문제 분류 자체가 이진탐색이긴 합니다만, 그걸 활용하기 위해서는 이진탐색을 이용한 풀이 로직을 이해해야 합니다.. 그런데 저는 이해가 잘 안되더라구요..ㅎㅎ  차라리 일반항으로 바로 찾아버리는게 낫다고 생각했습니다.

따라서 제가 생각하는 키 포인트는 다음과 같습니다.

• 달팽이는 요구하는 높이에 다다르면 더이상 미끄러지지 않는다. 즉, 높이를 기록한 배열에서 밤에 미끄러진 결과를 반영한 높이를 기록하는게 아니라, 그 날 최대로 올라간 높이를 기록해야 합니다.
• 일반항 : 낮과 밤에 정해진 만큼 올라가고 내려가기 때문에, 높이를 기록한 배열은 자동으로 등차수열이 됩니다. 참고로 등차수열의 일반항은 $a_{n}=a_{0}+(n-1)d$라고 알려져 있습니다.
• 이진 탐색 : 높이를 이용해 이진탐색을 할 수 있는데, 사실 이해가 잘 안갑니다.

 

 

일반항을 이용한 풀이

위에서 말했듯이, 달팽이가 올라갈 수 있는 최대 높이를 날짜별로 나열한다면 등차수열을 이룹니다. 백준의 예시에 따르면 다음과 같습니다.

$$2, 3, 4, 5, 6, ...$$

위 수열은 초항인 $a_{0}$가 2이며 공차가 $d = 2 - 1 = 1$인 수열이 됩니다. (첫째 날 낮에 최대 2m까지 올라갑니다. 첫째 날 밤에 1m 미끄러져 1m가 됩니다. 둘째 날 낮에 2m 올라가 4m가 됩니다. 밤에 1m 미끄러져 3m가 됩니다. 셋째 날 밤에 2m 올라가 6m가 됩니다. 밤에 1m 미끄러져 5m가 됩니다.)

그리고 등차수열의 일반항 공식은 다음과 같습니다.

$$a_{n}=a_{0}+(n-1)d$$

해당 문제에서 초항은 달팽이가 올라가는 높이(이하 up), 공차는 올라가는 높이 - 미끄러지는 높이(이하 down)이 됩니다.

우리 문제에 맞게 수정하면 다음과 같습니다.

$$a_{n}=up+(n-1)(up-down)$$

따라서 특정 높이 이상이 되는 첫 번째 항을 구하는 공식은 다음과 같습니다.

$$n\ge\frac{(height-up)}{(up-down)}+1$$

 

 

이진탐색을 이용한 풀이

(내용 넣기)

 

 

풀이 코드 (Java)

일반항을 이용한 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            String[] inputs = br.readLine().split(" ");
            int up = Integer.parseInt(inputs[0], 10);
            int down = Integer.parseInt(inputs[1], 10);
            int height = Integer.parseInt(inputs[2], 10);

            int day = (int) Math.ceil((height - up) / (up - down)) + 1;
            System.out.println(day);
        } catch (Exception e) {
        }

    }
}

우선, (height - up) / (up - down)의 결과가 딱 떨어지지 않는다면, 그 말은 결국 하루가 더 필요하다는 뜻입니다. 따라서 ceil()함수를 이용해 보정을 해줍니다.

 

 

이진탐색을 이용한 풀이 코드

(코드 및 설명 넣기)