문제 번호 2869번 : 달팽이는 올라가고 싶다 - JAVA [자바]

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

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

 

이 문제를 풀기에 오답을 정말 많이 냈습니다. 가장 큰 이유가 시간 초과인데요. 시간 제안이 굉장히 빡센 문제이기 때문에 시간을 맞추기 위해 두 가지 중요한 규칙이 있습니다.

 

1. 반복문을 사용하지 않는다.

2. Scanner를 사용하지 않는다.

 

두가지를 지켜 문제를 풀면 시간 안에 문제를 풀 수 있습니다.

 

정답을 보고 난 후에 코드리뷰 하겠습니다.

import java.util.*;
import java.io.*;

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 A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		
       int day = (V-A)/(A-B)+1;
        
		if((V-A)%(A-B) != 0) day++;

        System.out.println(day);
    }
}

 

먼저 눈에 보이는 BufferedReader에 대해 설명하겠습니다. BufferedReader은 Scanner보다 빠른 입력 함수입니다. 입출력에 관해서 왜 더 빠른지는 여기서 설명하진 않겠습니다. 일단은 Scanner보다 빠른 함수라고 이해하시면 됩니다. 

ButteredReader은 변수.readLine()로 사용하면 입력을 받을 수 있습니다.  저는 변수를 br로 선언했고 StringTokenizer로 입력을 받았습니다. 

StringTokenizer은 두번째 문자열을 기준으로 받은 문자열을 나누어 줍니다. 위에 코드는 하나의 공백으로 문자열을 나누어 준다는 뜻입니다. 그럼 이제 st에 해당 문자열이 공백을 기준으로 나누어서 들어가져 있을겁니다.

그 문자열을 차례대로 A,B,V 변수에 넣어줍니다. st.nextToken()을 사용하면 첫 번째 부터 다음 공백을 기준으로 나눈 문자열이 초기화 되게 됩니다.

 

두번째는 일수를 구하는 방법입니다. 원래는 while을 돌려서 해당 나뭇가지를 모두 오르면 break를 하는 형식으로 만들면 너무 편하겠지만 반복문을 사용할 수 없음으로 수학적인 로직이 필요합니다.

여기서 중요한 건 결국 달팽이가 나뭇가지 끝에 터지다운 하는건 낮이라는 겁니다.

무슨 말이냐면

만약 달팽이가 낮에 3올라가고 1떨어지고 7의 나뭇가지를 올라가고 있다고 가정해 봅시다.

그럼 그냥 낮을 기준으로 계산을 하면 됩니다.

첫째날 낮에 3을 올라가고

밤에 1 떨어지고

둘째날 낮에 5를 올라가고

밤에 1 떨어지고

셋째날 낮에 7을 올라가

3일째 되는 날 달팽이는 올라가는걸 끝내게 됩니다.

여기서 사실 밤에 떨어진다는 사실은 크게 상관이 없습니다. 

결국 올라가는 길이는 2(낮에 올라가는 길이 - 밤에 떨어지는 길이)이니깐요

 

만약 달팽이가 낮에 3올라가고 1떨어지고 8의 나뭇가지를 올라가고 있다고 다시 가정해 봅시다.

첫째 날 낮에 3을 올라고

밤에 1 떨어지고

둘째 날 낮에 5을 올라가고

밤에 1 떨어지고

셋째 날 낮에 7을 올라가

밤에 1 떨어지고

넷째 날에 8을 올라가

4일째 되는 날 올라가는 걸 끝내게됩니다.

 

여기서 1번 가정과 2번 가정의 다른 점은 수열을 쭉 세웠을 때 그 그 수에 나뭇가지 길이가 있는지 없는지에 차이입니다.

이 말을 좀 더 풀어서 해석하면 다음 그림과 같이 됩니다.

수열 공식으로 봤을때 결국 도달하는 길이는 수열에 딱 맞게 답이 나와있지 않음으로 그 수로 딱 떨어지는 안떨어 지는를 확인해야 합니다.

조금 설명이 중구난방이지만 다시 원점으로 돌아와서 결국 며칠을 올라갔는지 확인하는 방법은

 

a + d(n-1) > v

a : 첫날에 올라간 높이

d : 올라간 높이 - 내려온 길이

n : 구해야 하는 날짜

v : 나뭇가지 길이

즉 위에 경우를 넣어서 식을 만들어 보면

3 +(3-1)(n-1) > 7

(3-1)(n-1) > 7 - 3

(n-1) > (7-3)/(3-1)

n > (7-3)/(3-1)+1

다시 변수를 넣은 식으로 변경하면

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

가 됩니다. 

(7-3)/(3-1) +2를 하게되면 나머지 없이 딱 3이 나오게 됩니다.

반면 

올라가야 하는 높이가 8인 경우에는

(8-3)/(3-1)+1에서 나머지가 생기게 됩니다. 하루를 더 올라가야 한다는 뜻이죠 그래서 위에 식에서 걸린 날에 +1을 해주어 해결하였습니다.

 

설명이 많이 부족합니다. 이해가 안되시는 점이 있다면 댓글로 남겨주세요.