728x90
반응형
https://www.acmicpc.net/problem/2869
이 문제^^ 참 욕나온다.
사실 문제만 보면 while문 돌리면 되는 간단한 문제라고 생각하겠지만 이 문제의 함정은 "시간 제한"에 있다..ㅋ
0.15초 실환가^^
0.15초인데다가 입력 조건을 보면 숫자 범위가 10억이다..ㅋ
반복문 절대 불가.. 쓰면 무조건 시간 초과 뜬다..
무적권 수식 하나로 마무리 해야한다..
일단 처음에 짜서 통과한 코드다!
import java.util.*;
import java.io.*;
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 res = (int)Math.ceil((double)(V-A)/(A-B));
System.out.println(res+1);
}
}
어떤 원리냐면,,
하루동안 A만큼 올라가고 B만큼 떨어지니까 (A-B)씩 계산하면 되는데,
이때 주의할 점이 A만큼 올라갔을 때 정상에 도달할 수 있으면 거기서 끝내야한다는 것이다.
그럼 이 문제에서 핵심은 마지막에 A를 올라가면 정상에 올라가서 끝낼 수 있느냐, 없느냐를 따지는 것이다.
V에서 A를 뺀 값을 A-B로 나누게되면 ? 만약에 나누어 떨어지면 딱 A만큼만 더 올라가면 된다는 뜻이니까 몫+1을 해주면 되고
나누어 떨어지지 않는다면 A만큼 올라간 것보다 좀 더 올라가야한다는 뜻이므로 무조건 올림해주면 된다. 그 후에 올림해준 값+1 !
근데 여기서 Math.ceil을 안쓰고 (V-A) % (A-B) 가 0인지 확인하는 코드 넣으니까,, 바로 시간초과가 떴다.. 허허 ..
위의 설명을 영상으로도 제작해봤다! 혹시라도 위의 설명이 이해가 안되시면 아래 영상을 보시는걸 추천한다!
다른 분들은 (V-B) / (A-B)로 짜셨던데.. 내가 아무리 머리를 굴려도 명쾌하게 이해가 되진 않는다.
추후.. 이해하면.. 이 부분에 대해서도 포스팅하겠다,,ㅠ
728x90
반응형
'알고리즘 (for 코딩테스트) > 백준_자바 (Java)' 카테고리의 다른 글
[Java 자바] 백준 알고리즘 1920번 답 : 수 찾기 (0) | 2021.09.04 |
---|---|
[Java 자바] 백준 알고리즘 15829번 답 : Hashing (1) | 2021.09.03 |
자바 실행시간 줄이는 Tip | 자바 백준 시간초과 시 해볼만한 시도 | 자바 초보자 (0) | 2021.09.01 |
[Java 자바] 백준 알고리즘 10989번 답 : 수 정렬하기3 (0) | 2021.09.01 |
자바 2차원 배열 정렬하기 | Java 2차원 배열 정렬하기 (0) | 2021.08.29 |
최근댓글