[백준 2869] 달팽이
문제: https://www.acmicpc.net/problem/2869
문제 이해:
(1 ≤ B < A ≤ V ≤ 1,000,000,000)
낮에 a 올라갈 수 있고, 밤에는 b 미끄러진다. 그러나 v미터인 정상에 도착하면 밤이어도 미끄러지지 않는다.
하고자 하는 것:
그렇다면 하루에 올라가는 미터는 a-b,
그러나 낮에 정상에 올라가면 밤에 떨어지지 않는 부분을 넣어야 됨.
코드: (시간 초과 남 )
package till;
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scan = new Scanner(System.in);
int day= scan.nextInt();//낮에 올라가는 미터
int night= scan.nextInt();//밤에 미끄러지는 미터
int top=scan.nextInt();//정상 높이
int result = Snail(day, night, top);
System.out.println(result);
}
public static int Snail(int a, int b, int v) {
int total=0, temp=0, count=0;
int x=v/a;
while(true){
temp+=a;
if(temp>=v){//정상을 넘거나 도달하면 -b 하지 않고 걸리는 일수 ++하고 while문 종료
total++;
break;
}
temp-=b;
total++;
count++;
}
return total;
}
}-> 노가다식으로 하나하나 다 계산하는 방법 말고 계산 횟수를 줄일 수 있는 규칙을 발견해야 한다고 생각함
최소로 올라갈 수 있는 높이 : a-b
최대로 올라갈 수 있는 높이: a
올라가야 하는 높이 : v
최대로만 올라갈 수 있을 때 나오는 일수부터~ 최소로만 올라갈 수 있을 때 나오는 일수까지
코드: ( 나름 경우의 수를 줄였다고 생각했는데 아직도 시간 초과됨 )
package till;
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scan = new Scanner(System.in);
int day= scan.nextInt();//낮에 올라가는 미터
int night= scan.nextInt();//밤에 미끄러지는 미터
int top=scan.nextInt();//정상 높이
int result = Snail(day, night, top);
System.out.println(result);
}
public static int Snail(int a, int b, int v) {
int total=0, temp=0, count=0;
int x=v/a;//밤이 없다고 생각했을 때, 낮으로 올라갈 수 있는 길이만으로 정상에 도달할 수 있는 일수 구하기
total=x;
temp=x*(a-b);
while(true){
temp+=a;
if(temp>=v){//-b 하기 전에(=밤이 오기 전에) 정상을 넘거나 도달하면 걸리는 일수 ++하고 while문 종료
total++;
break;
}
temp-=b;
total++;
count++;
}
return total;
}
}답 봄:
https://yahohococo.tistory.com/28
https://lazyren.tistory.com/40 [Lazy Ren's Blog]
문제 정리-->하루에 a-b씩 총 v미터를 올라가면 된다.
생각 못한 것:
결국엔 v-b미터를 목표지점이라고 생각해도 된다는 것
-> why?) 달팽이가 목표 지점에 도달한 날에는 미끄러지는 것을 감안하면 안 되니 총 v-b 미터를 올라가게 되는 것과 같기 때문
(v-b)/(a-b)로 식을 세울 수 있다는 것
만약(v-b)/(a-b)를 했는데 소수점이 생길 경우는 즉, 하루를 +1해야 한다는 것
파이널 코드:
package till;
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scan = new Scanner(System.in);
int day= scan.nextInt();//낮에 올라가는 미터
int night= scan.nextInt();//밤에 미끄러지는 미터
int top=scan.nextInt();//정상 높이
int result = Snail(day, night, top);
System.out.println(result);
}
public static int Snail(int a, int b, int v) {
int total=0;
total=(v-b)/(a-b);
if((v-b)%(a-b)!=0)
total++;
return total;
}
}bufferedreader 사용한 버전
package till;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main (String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine());
int day= Integer.parseInt(st.nextToken());//낮에 올라가는 미터
int night= Integer.parseInt(st.nextToken());//밤에 미끄러지는 미터
int top=Integer.parseInt(st.nextToken());//정상 높이
System.out.println(Snail(day, night, top));
}
public static int Snail(int a, int b, int v) {
int total=0;
total=(v-b)/(a-b);
if((v-b)%(a-b)!=0)
total++;
return total;
}
}역시나 bufferedreader가 훨씬 빠르고요~
채점 번호 아이디 문제 번호 결과 메모리 시간 언어 코드 길이 제출한 시간
13665216 soojin20215 2869 맞았습니다!! 12908 72 Java / 수정 815 3분 전
13406364 soojin20215 2869 맞았습니다!! 14228 108 Java / 수정 583 24일 전
Math.ceil 메소드 사용한 버전
package till;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main (String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine());
int day= Integer.parseInt(st.nextToken());//낮에 올라가는 미터
int night= Integer.parseInt(st.nextToken());//밤에 미끄러지는 미터
int top=Integer.parseInt(st.nextToken());//정상 높이
System.out.println(Snail(day, night, top));
}
public static int Snail(int a, int b, int v) {
int total=0;
total= (int) Math.ceil((v-b)/(a-b));
return total;
}
}틀렸습니다 나옴!!!
((v-b)/(a-b)) 이거를
((double)(v-b)/(double)(a-b))로 해줘야지 나눗셈이 정상적으로 됨
수정한 코드
package till;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main (String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine());
int day= Integer.parseInt(st.nextToken());//낮에 올라가는 미터
int night= Integer.parseInt(st.nextToken());//밤에 미끄러지는 미터
int top=Integer.parseInt(st.nextToken());//정상 높이
System.out.println(Snail(day, night, top));
}
public static int Snail(int a, int b, int v) {
int total=0;
total= (int) Math.ceil(((double)(v-b)/(double)(a-b)));
return total;
}
}
Comments