[2869] 달팽이는 올라가고 싶다

난이도: ★★★★☆ • solved on: 2025-07-10

---

문제 요약

• 문제 유형: 수학, 구현
• 요구사항: 달팽이가 낮에 A미터 오르고 밤에 B미터 미끄러질 때, 높이 V미터 나무 막대를 모두 올라가려면 며칠이 걸리는지 구해야 한다.

---

사용 개념

1. 자료구조

   • 없음 (단순 변수 사용)

2. 알고리즘/기법

   • 단순 수식 변형, 나눗셈 및 올림(ceil) 연산

3. 핵심 키워드

   • 그리디, 반복 최소화, 수식 최적화

---

풀이 아이디어 및 코드

방법 1: 반복문 (A-B)의 몫에 따른 분기 설정

1. 문제 분해

• (a-b)만큼 반복적으로 이동해서 v에 도달할 때, 밤에 미끄러지는 것과 딱 맞는 조건을 세분화해 체크
• 불필요하게 경우의 수를 분기하므로 코드 복잡도가 증가

2. 핵심 로직 흐름
   • 나눗셈, 나머지, 분기(if-else)로 접근
3. 예외 처리
   • 나누어떨어지는 경우, v%(a-b)<=b 등 꼼꼼히 고려해야 해서 실수 위험 높음

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tokens = br.readLine().split(" ");
        int a = Integer.parseInt(tokens[0]);
        int b = Integer.parseInt(tokens[1]);
        int v = Integer.parseInt(tokens[2]);
        if (v % (a - b) == 0) {
            System.out.print(v / (a - b) - (b / (a - b)));
        } else if (v % (a - b) <= b) {
            System.out.print(v / (a - b) - (b / (a - b)));
        } else {
            System.out.println(v / (a - b) + 1);
        }
    }
}

---

방법 2: 수식 기반 정수 연산 (조건문 최소화)

1. 문제 분해
   • 달팽이가 하루에 실제로 올라가는 높이: a - b
   • 마지막 날에는 밤에 미끄러지지 않으므로, V - A까지만 밤/낮 패턴 반복
   • 마지막 오르는 날(낮)은 예외이므로, V - A까지는 (a-b)만큼 이동, 마지막에 한번 A만큼 올라서 끝남
2. 핵심 로직 흐름
   * (V - B) 미터를 (A - B)씩 매일 올라감
   → 최소한의 일수 = ceil((V - B) / (A - B))
   → 올림(ceil) 연산이 반드시 필요 (정확히 딱 맞아도 하루 더 필요 없음)
3. 예외 처리
   • 입력에서 항상 A > B, V > B 보장

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

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 days = (v - b) / (a - b);
        if ((v - b) % (a - b) != 0) days += 1;

        System.out.println(days);
    }
}

---

---

시간·공간 복잡도

방법 1 & 방법 2

• 시간 복잡도: O(1)
• 공간 복잡도: O(1)

---

어려웠던 점

• 반복문 없이 수식만으로 문제를 풀려 하니 직관적인 해석이 힘들었고, if문을 어떻게 구성해야 하는지 고민이 많았음.
  → 방법1로 접근할 때 직관적이지 않다 보니 힘들었음

• 조건 분기마다 실제로 어떤 입력에서 해당 줄이 실행되는지 테스트하면서 흐름을 잡는 게 어려웠다.

---

배운 점 및 팁

• 마지막 날에는 미끄러지지 않는다는 점을 인지하고, "전체 길이에서 밤에 미끄러지는 만큼만 빼서" 수식으로 한 번에 해결할 수 있다는 점을 배웠음.
• "올림" 연산을 구현할 때 (값 + 몫-1)/몫 패턴을 활용하거나, 나머지가 있으면 하루를 더 더하는 방식이 직관적임.
• 조건문 분기보다는, 최대한 단순한 수식으로 한 줄에 표현하는 게 코드 관리에 좋음. (방법1의 조건문 → 방법2의 ceil 함수로 통합)

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/2869
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 1074번 Z (Z, 재귀, 수식 변형)
  • 손익분기점 (손익분기점, 수학적 분석)

• 확장 문제 (GPT 추천):

  • 계단 오르기 변형 문제: 하루에 오르는/미끄러지는 값이 매일 달라질 때 최단 기간 구하기
  • 여러 구간/단계별로 이동 방식이 바뀌는 상황에서의 최소 반복 계산