[실전알고리즘] 달팽이는 올라가고 싶다 (어렵다)

구글링 구글링!!!!! 좀 해라 오류난 부분 구글링 하면 나온다.

항해99_실전_알고리즘 주차 문제와 해결_3 (너무 어려워)

[JAVA]

문제 참고 : https://www.acmicpc.net/problem/2869

문제 : [달팽이는 올라가고 싶다]

문제 설명

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

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

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

입력

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

출력

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

---

정답 (정리 잘 된 거)

https://st-lab.tistory.com/75

- 이번 문제는 특히나 시간 제한이 엄청 빡빡하기 때문에 BufferedReader 로 써주는 것이 가장 좋다.

BufferedReader 을 쓰는 방식이다.

그리고 반드시 자료형 타입을 잘 보아야 한다.

br.readLine() 은 문자열로 데이터를 읽으며, StringTokenizer 로 문자열 분리 후 해당 토큰을 꺼내서 쓸 때 int 형으로 쓰고자 한다면 Integer.parseInt()로 String 을 int 형으로 변환시켜준다.

 

- 참고사항

BufferedWriter에서 정수를 출력할 때는 String으로 변환해 줘야 합니다.

https://dev-note-97.tistory.com/58

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
		int up = Integer.parseInt(st.nextToken());
		int down = Integer.parseInt(st.nextToken());
		int length = Integer.parseInt(st.nextToken());
 
		int day = (length - down) / (up - down);
		if ((length - down) % (up - down) != 0)
			day++;
 
		System.out.println(day);
	}
}

 

- 시간 초과 된 거 (Scanner)

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		int up = in.nextInt();		// A
		int down = in.nextInt();	// B
		int length = in.nextInt(); 	// C
 
		int day = (length - down) / (up - down);
        
		// 나머지가 있을 경우 (잔여 블럭이 있을 경우)
		if ((length - down) % (up - down) != 0) {
			day++;
		}
		System.out.println(day);
	}
}

 

내가 해 본 거

1. 문제 분석

- 달팽이는 높이가 V미터인 나무 막대를 올라갈거다.

-달팽이는 낮에 A미터 올라간다. / 밤에는 잠을 자는 동안 B미터 미끄러진다.

/ 정상에 올라 간 후에느 미끄러지지 않는다.

- 달팽이가 나무 막대를 모두 올라가려면 며칠이 걸리나?

 

2.규칙 찾기 & 정리

- A, B, V 값 입력 받기 (1 ≤ B < A ≤ V ≤ 1,000,000,000)

예제 입력	예제 출력
1)  A : 2, B : 1, V : 5	4 (일)
2)  A : 5, B : 1, V : 6	2 (일)

1) V=5미터인 까지 도달하자

=> 낮 2 + 밤 (-1) + 낮 2 + 밤 (-1) + 낮 2 + 밤 (-1) + 낮 2 => 4일 째 되는 날 도달

 

2) V=6미터인 까지 도달하자

=> 낮 5 + 밤 (-1) + 낮 5 => 2일 째 되는 날 도달

 

3. 코딩화

sum = 0;

day = 0;

while (sum < V) {

  sum += A;

  if(A>V) {

    day++;

    break;  

  }

  sum += B;

  day++;

}

 

4. 구현

- 결과 제대로 나오는데 백준에서는 틀렸다고 나온다 ㅠㅠ

//백준 알고리즘 JAVA11버전

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("1 ≤ B < A ≤ V ≤ 1,000,000,000 - A, B, V를 입력해주세요");
        int A = sc.nextInt();
        int B = sc.nextInt();
        int V = sc.nextInt();

        int result = Is_Prime(A, B, V);
        System.out.println("달팽이가 막대를 다 올라간 날 : "+ result);
    }

    private static int Is_Prime(int A, int B, int V) {
        int sum = 0;
        int day = 0;

        while (sum < V) {
            sum += A;
            System.out.println("첫번째 : sum  "+ sum);
            if(sum>=V) {
                day++;
                System.out.println("첫번째 : day  "+ day);
                break;
            }
            sum -= B;
            System.out.println("두번쨰 : sum  "+ sum);
            day++;
            System.out.println("두번째 : day  "+ day);
        }
        return day;
    }
}