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

www.acmicpc.net/problem/2869

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

- 문제 –

---

- 풀이 과정 –

문제를 간단히 읽어보면 달팽이가 일정 높이까지 가는데 걸리는 일 수를 계산하는 문제입니다.

하루 중 낮에는 올라갔다가(up) 밤에는 미끄러 지기에(down) up-down을 하면 달팽이가 하루 동안 이동하는 거리를 계산할 수 있습니다.

 

따라서 나무 길이를 length라고 할 때 length/(up-down)을 하여 며칠이 걸리는지 계산할 수 있는데 이렇게 계산하면 오답처리가 됩니다.

 

왜냐하면 문제에서 ‘정상에 올라간 후에는 미끄러지지 않는다’는 조건 때문입니다.

예를 들어 up=2, down=1, length=5의 값이 입력된다면 이 풀이 과정을 쭉 나열해보겠습니다.

정상에 도착하는 마지막 날에는 미끄러지지 않아야 하는데 계산식[length/(up-down)]에는 마지막 날까지 미끄러져 맞지 않는 것입니다.

 

따라서 양쪽변에 down값을 빼줌으로써 계산식을 작성하면 (length-down)/(up-down)이 됩니다.

 

(length-down)/(up-down)의 몫은 달팽이가 올라가기 위한 최소한의 일 수가 됩니다.

(length-down)%(up-down)의 나머지는 두 가지 상황이 생깁니다.

    1.  (length-down) % (up-down)의 나머지가 0으로 떨어지는 경우

    2.  (length-down) % (up-down)의 나머지가 남는 경우

나머지가 남는 경우는 최소한의 일 수에서 잔여 거리가 남은 것입니다. 하루를 더 소요해서 up을 해야 하기에 조건문을 추가하여 문제를 풀 수 있습니다.

 

이렇게 반복문 없이 연산만을 통해 출력할 수 있어 수행시간이 매우 짧아지는 장점이 있습니다.

---

- 소스 코드 -

package com.test;
 
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) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int up=Integer.valueOf(st.nextToken());
            int down=Integer.valueOf(st.nextToken());
            int length=Integer.valueOf(st.nextToken());
            
            int count=(length-down)/(up-down);  // 최소 일 수
            
            if((length-down)%(up-down)!=0) count++; // 남은 거리가 있는 경우 하루 증가
            System.out.println(count);
        }catch(IOException e) {
            e.printStackTrace();
        }
    }
}

 

[참고 사이트] https://st-lab.tistory.com/75