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

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

링크

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

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

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력
첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력
첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

접근방법

  문제에서 달팽이는 오르고, 떨어지는 순간을 매일 반복한다. 해당 달팽이가 막대기까지 도달하는 시간을 출력하는 것이 문제이다. 생각해야 할 것은 아침에 막대 끝에 도착한다면, 밤에 떨어지는 것은 생각을 안 해도 된다는 점이다. 이런 부분에 대해 생각해보고 풀이에 접근하자.

풀이

 하루 단위로 계산을 하자니, 낮에는 도착하는 경우를 고려해야 한다. 접근방법에서 언급했듯, 낮에 도착만 하면, 저녁에 떨어져도 상관이 없다. 그럼 생각을 달리해보자.

막대에 도착하는 전날 저녁, 달팽이가 B만큼 떨어지고 나서의 길이가 낮에 갈 수 있는 A만큼만 남겨둔다면, 매일 A만큼 증가했다가 B만큼 떨어져도 상관이 없다.

따라서, 올랐는데 걸리는 시간을 구하기 위해, 길이 V를 분리한다.

1.  V-A 만큼의 거리
2.  A 만큼의 거리

V-A 만큼의 거리는 하루 단위로 계산해도 상관이 없다. 어차피 하루 단위로 움직여도, 종점까지 이동하지 않으므로 문제가 없다. 따라서 V-A만큼 움직이는 시간을 구하고, A만큼은 낮에 갈 수 있으므로 하루를 더 해주면 된다.

실패 원인

  문제를 접근했을 때, 반나절 단위로 분리하여 반복문을 통해 정답을 도출했다. 그러나 시간 초과에 걸려버렸다. 문제에서 제시한 제한 시간은 0.15 초이다. 문제의 범위도 크고, 반복문의 동작 횟수가 제수의 크기에 따라 상당히 차이가 나기 때문에, 반복문은 문제에서 요구하는 방식이 아니었다.  

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main(){
        Scanner sc = new Scanner(System.in);
        int morning = sc.nextInt();
        int night = sc.nextInt();
        int target = sc.nextInt();

        int result = solution(morning,night,target);
        System.out.println(result);
    }


    public int solution(int morning ,int night,int target){
        int day = 0;

        while(true){
            day++;
            if(target - morning <= 0){
                break;
            }
            target -=(morning-night);


        }

        return day;
    }
}

코드

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 {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine()," ");

        int morning = Integer.parseInt(stk.nextToken());
        int night = Integer.parseInt(stk.nextToken());
        int target = Integer.parseInt(stk.nextToken());

        int result = solution(morning,night,target);
        
        System.out.println(result);
    }


    public int solution(int morning ,int night,int target){

        //일단 나눈다
        int day = 0;
        int diff = morning - night;
        int semi_target= target -morning;
        day++;

        //나머지가 존재하는 경우는 +1 해주면 끝남
        if( semi_target % diff != 0){
            day+= semi_target/diff +1;
        }else{
            //나머지가 존재하지 않는 경우 (딱맞아 떨어짐)
            day+= semi_target/diff;

        }
        return day;

    }
}

결과

 모든 알고리즘 문제가 그러하듯, 방법은 다양할 수 있다. 그러나 요구사항에 맞는 로직을 만들기 위해, 생각하고 만드는 습관이 필요한 것을 느꼈다.

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.