-
2869 - 달팽이는 올라가고 싶다알고리즘 2023. 5. 23. 12:21728x90
https://www.acmicpc.net/problem/2869
2869번: 달팽이는 올라가고 싶다
첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)
www.acmicpc.net
문제요약
- 달팽이가 낮에 A만큼 올라감.
- V 높이에 도달하면, 더이상 미끄러지지 않는다.
- 도달못한다면, 밤에 B만큼 미끄러진다.
- 1 ≤ B < A ≤ V ≤ 1,000,000,000
- 달팽이가 V 높이까지 올라가는데 걸리는 날을 출력
해당 문제는
단순히 while문을 돌면서 올라간 높이를 계속 누적합하고,
이때의 높이가 V인지를 확인한 후에, 아니라면 B 만큼 빼주고,
하루를 더해주고,...
이런 방법으로는 변수에 해당하는 값을 시간내에 출력하지 못한다.
즉, 문제를 몇번의 연산으로 날짜 계산으로 이어질 수 있게끔 코드를 짜야 했다.
이후 내가 생각한 공식은
(UP - DOWN) ==> 한번에 도달 못할 시, 하루에 올라가는 높이라면,
도달했을 때는
(UP - DOWN) m/day + UP m/day = 목표도달치(V) m 가 되는 것이다.
정리하면,
(V - UP) m = (UP - DOWN) m/day * day 의 식에서의 연관성을 찾는 것으로 시작했다.import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int up, down, height; up = sc.nextInt(); down = sc.nextInt(); height = sc.nextInt(); // 도달하기 하루전 날짜 int day = (height - up) / (up - down); // 도달하기 하루 전, 남은 거리 int reg = height - day * (up - down); // 도달하기 하루전 남은거리가 up보다 작으면 하루만 더 올라가면 끝 if(reg <= up){ System.out.println(day + 1); }else{ System.out.println(day + 2); } } }
느낀점
나누는 과정에서 day가 최대치로 이미 계산되어지니까 하루나 이틀 더 올라가면 된다는 가정에서 시작한 코드이다.
기존에는 식으로 한번에 처리될 수 있는 것들도 거의 반복문을 돌리면서 처리했지만, 그 범위가 클 경우 시간이 많이 걸린다는 것을 알게되었다. 수학적 공식으로 접근했을 때, 쉽게 풀릴 수 있는 문제는 그 방법으로 접근하면 된다는 것을 알게 되었다.
'알고리즘' 카테고리의 다른 글
1110 - 더하기 사이클 (2) 2023.05.24 1929 - 소수 구하기 (0) 2023.05.24 10250 - ACM 호텔 (0) 2023.05.24 4948 - 베르트랑 공준 (0) 2023.05.23 2839 - 설탕배달 (0) 2023.05.23