[문제풀이 후기] 백준 #2869 - 달팽이는 올라가고 싶다

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

 

기본 상위 코드

import { readFileSync } from "fs";

const input = readFileSync(0).toString().trim();	// 입력값

// up: 올라간 높이, down: 내려간 높이, target: 목표 높이
const [up, down, target] = input.split(" ").map(Number);

 

첫 번째 시도 (결과 : 실패)

 

접근 방식

1. 일단 올라가기
2. 목표 높이 도착 여부 확인
  - 도착 O : 종료
  - 도착 X : 내려가기
3.  일 수 ++

// dayCount: 일 수, currentHeight: 현재 높이
let [dayCount, currentHeight] = [0, 0];

// 현재 높이 >= 목표 높이가 될 때까지
while (currentHeight < target) {
  // 일단 up
  currentHeight += up;

  // 올라갔지만 아직 남은 경우 (그 날 종료 실패)
  // 마저 down 한 뒤 마무리
  if (currentHeight < target) {
    currentHeight -= down;
  }

  dayCount++;
}

console.log(dayCount);

 

실패 원인 : 시간 초과

 

아무래도 반복문을 사용하기에 시간복잡도가 O(n) 이 나오는데, 이게 문제인 것 같다.

 

그렇다면 반복문을 사용하지 않고 푸는 방법이 있다는 뜻일텐데... 그게 뭘까

---

규칙 

# 용어 정의
u : 올라간 높이 / d : 내려간 높이
T : 목표 높이 / C : 일 수

# 목표 높이에 도달하는 최소 시간
(u - d) + (u - d) + ... u >= T
-> uC - d(C - 1) >= T
-> uC - dC + d >= T
-> C(u - d) >= T - d
-> C >= (T - d) / (u - d)

# 결론
(T - d) / (u - d) 를 했을 때
- 값이 정수인 경우 : 그 날 종료 (C = 결과값)
- 값이 정수가 아닌 경우 : 다음 날 종료 (C = 결과값 + 1)

-> Math.ceil(C) 출력

 

두 번째 시도 (결과 : 성공)

const dayCount = (target - down) / (up - down);

console.log(Math.ceil(dayCount));

 

후기

풀이 과정을 어떻게 설계하냐에 따라 이렇게 구현 난이도와 속도가 달라지다니..
모든 문제에 숨어있는 규칙을 효율적으로 빨리 찾는 방법이 있을까?