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

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

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

---

• 문제

 

 

 

음.. 문제는 쉬워보이는 것 같은데 정답 비율이 엄청 낮다..

여기서 가장 중요한 키포인트가 몇가지 있으니 아래 알고리즘 설명을 꼭 보시길 바란다.

 

---

• 2가지 입력방법을 이용하여 풀이한다.

 

 

Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다.

 

---

• 알고리즘 [ 풀이 방법 ]

 

이 문제를 풀기에 앞서 왜 정답 비율이 낮은지 잠깐 볼 필요가 있다.

 

 

 

자바의 경우 알고리즘 자체가 틀린 것과 시간 초과된 제출자가 매우 많다.

 

1. 알고리즘을 틀린 것은 다음과 같은 조건 때문이다.

 

 

위 조건 때문에 낮에 올라가는 길이와 밤에 내려오는 길이를 단순히 빼서 나눗셈하면 안된다는 것이다.

 

 

2. 그리고 시간초과가 많은 이유는 다음과 같다.

 

 

 

 

시간 제한이 0.15초, 즉 150ms 이내로 프로그램이 종료되어야 한다는 것이다.

 

백준 문제를 많이 풀어봤다면 알겠지만,

보통 입력할 때 Scanner 와 BufferedReader, 이렇게 두 케이스로 나뉘게 된다.

 

그 중 Scanner 를 이용해 풀었던 사람이라면 기본적으로 100ms 는 넘길 수밖에 없다는 것을 알 것이다.

 

그렇다고 Scanner 로 이 문제를 못 푸는 것은 아니나,

Scanner 로 풀면서 알고리즘이 복잡한 경우는 어김없이 시간초과가 발생해버린다는 것.

 

그렇기에 Scanner 로 풀려면 "최적화된 알고리즘" 이 필요하다.

 

그럼 어떻게 수학적으로 풀 것인지 한 번 확인해보자.

---

먼저 세 정수 A, B, V 가 주어진다.

 

읽기 쉽게 A = up, B = down, V = length 라고 하자.

그리고 주어진 범위는 다음과 같다.

 

( 1 ≤ down < up ≤ length ≤ 1,000,000,000 )

 

 

 

만약에 아래와 같이 풀면 100% 틀린다.

print( length / (up - down) );

 

 

 

예제 입력에서 주어진 값인 2 1 5 을 위 식에 대입해보면 결과값은 5가 나온다.

 

하지만 실제로 걸리는 일 수는 4일이다.

이는 "정상에 올라간 후에는 미끄러지지 않는다" 라는 조건 때문이다.

 

즉, 그림으로 보면 다음과 같다.

 

 

 

 

 

 

즉, 낮에 만약 정점에 도착하면 더이상 미끄러지지 않는다는 것이다.

다른 예시를 들어보자.

up = 3

down = 1

length = 7

 

이렇게 주어졌을 때와,

up = 3

down = 1

length = 8

 

이렇게 주어진 두 케이스를 보자.

 

 

 

즉 up 일 때 나머지 블럭이 남아있다면 하루가 더 소요된다는 것이다.

그리고 가장 중요한 것이 있다.

down 은 항상 up 보다 횟수가 하나 작다.

 

 

 

즉, 이렇게 생각 할 수 있을 것이다.

"마지막에 도달할 때의 down 의 경우의 수(길이)를 뺀다."

 

엥? 왜 down 을 빼주는거죠?? 라고 묻는다면 잘 생각해보자.

 

기본적으로 만약에 정점에 도달 할 때 미끄러지지 않는다는 조건이 없다면 다음과 같이 쉽게 짤 수 있다.

length / ( up - down )

 

즉, up 과 down 의 차를 length 에서 나누면 잔여블록과 상관 없이 무조건 몫만 반환하게 된다.

 

근데, 문제에서 분명히 정점에 도달하면 미끄러지지 않는다는 조건이 붙어있다.

즉, 잔여 블록이 없으면 문제가 안되지만, 만약에 잔여블록이 있다면? 그러면 한 번 다시 미끄러진 다음에 올라가야 한다는 것이다.

 

이로써 up-down 의 차이 값보다 작은 나머지가 존재하면 다음날 up 때 올라가야하는 경우가 발생한다.

 

결과적으로 down 을 뺌으로서 up 과 down 의 차이를 나눈 몫은 최소한의 일(日) 수가 된다.

 

그리고 나머지에 대해서는 다음과 같은 두 가지 상황이 생긴다.

1. ( length - down ) % ( up - down ) 가 정확하게 0 으로 떨어지는 경우
2. ( length - down ) % ( up - down ) 가 나머지가 남는 경우

 

위 예시로 본다면 아래와 같다.

1. ( 7 - 1 ) % ( 3 - 1 ) = 0
2. ( 8 - 1 ) % ( 3 - 1 ) = 1

 

전체 길이에서 down 값을 빼고, up - down 을 나누면  둘 다 몫은 3 이다.

( 7 - 1 ) / ( 3 - 1 ) = 3

( 8 - 1 ) / ( 3 - 1 ) = 3

 

그러나 길이가 8일 경우 down 을 빼고 ( up - down ) 을 했는데 나머지가 생긴다.

 

이유는 up 과 down 의 차이 값으로 정확히 나누어 떨어지는 것이 아니라 아직 잔여 블럭이 남았기 때문이다.

그렇기 때문에 down 을 한 번 더 하게 되고, 자연스레 up 또한 한 번 더 하게 되는 것이다.

 

즉, 하루가 더 소요 되는 것이다.

 

그렇기 때문에 다음과 같이 조건문에 따라 출력값이 달라진다는 것이다.

 

int day = (length - down) / (up - down);

// 나머지가 있을 경우 (잔여 블럭이 있을 경우)
if( (length - down) % (up - down) != 0 ) {
	day++;
}

 

이렇게 짜면 굳이 반복문 없이 연산만을 통해 바로 출력할 수 있어 수행시간도 매우 짧아진다는 장점이 있다.

 

 

그럼 한 번 코드를 보자.

 

 

---

• 풀이

- 방법 1 

 

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);
	}
}

 

 

생각보다 간단하죠?

---

- 방법 2 

BufferedReader 을 쓰는 방식이다.

 

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

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

 

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);
	}
}

 

 

 

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

 

---

• 성능 차이

 

위에서 부터 순서대로

 

채점 번호 : 18843266  -  BufferedReader

채점 번호 : 18843262  -  Scanner

 

시간을 보면 BufferedReader 와 Scanner 의 성능차이를 볼 수 있다.

 

BufferedReader 로 짠다면 반복문으로 up 과 down 을 length 에서 빼면서 짜도 통과가 되지만,

Scanner 로 한다면 아마 시간초과가 날 것이다.

그렇기 때문에 Scanner 로 풀고자 한다면 수학 연산으로 바로 출력할 수 있도록 짜야할 것이다.

---

• 정리

 

생각보다 아주 단순한 문제다.

다만 문제만 대충 보고 푼다면 충분히 틀릴 수 있다고 보인다.

(그렇기 때문에 정답 비율이 낮았을거라 확신한다..)

 

그러니 앞으로 시간제한과 최소한의 수행시간을 생각하는 습관을 갖는 것이 무엇보다 중요할 것이다.