2869번 문제 : 달팽이는 올라가고 싶다

전형적인 어릴 때 많이 보던 수학문제 !

를 코딩으로 하게 됐당... 쉬워보이지만 시간이 상당히 짧아서 뭔가 방법을 찾아야할 것 같다.

 

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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 current = 0; //달팽이의 현위치
		int day = 1;
		while(true) {
			if(current <V) {
				current += A; //A만큼 올라가고
				if(current >=V)
					break;
				else
					day++;
				current-=B; //B만큼 미끄러짐
			}
		}
		System.out.println(day);
	}
}

완전 간단히 풀었지만 시간초과가 나왔따 ㅋㅋ

이것도 역으로 생각하는 방법 ? .. 음 흐음 ..

마지막 높이를 딱 찍어놓고 

올라가는 높이 A - 미끄러지는 높이 B를 해서 몇 번이나 쌍으로 필요한지를 day에 더해넣고

모자른 거 A로 더하고 day하나 더 추가 !

 

그러다 갑자기 이진탐색을 해야되는게 생각났따 !

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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 high = V-A;
		int low = 0;
		int mid = 0;
		int result = V;
		while(low<=high) {
			mid = (high+low)/2;
			
				if(mid*(A-B) >=V) 
					high = mid -1;
				else {//올라갔는데 아직 길이가 모잘르긴해
					if(mid*(A-B)+B >=V) { //B를 빼지않았을 때 안 모잘라지면 그냥 그대로 끝
						break;
					}
					else { //B까지 빼봤는데도 여전히 모자르다면
						if(V-mid*(A-B) <=A) { //모자르긴 한데 A로 한 번 커버가 가능하면
							mid += 1;
							break;
						}
						else //커버 안 되면 수 높여서 다시 연산
							low = mid+1;
					}
				}
		}
		System.out.println(mid);
	}
}

완성해서 예제 잘 나오고 문제도 돌아가는데 틀렸대 ~~~~ 왜일까 ~~~

자료형인가 싶어서 고쳐봤는데 틀렸당 26퍼에

 

일단 이 코드 질문 남겨놨다

글 읽기 - 26%에서 틀렸다고 나옵니다. 혹시 반례를 알려주실 수 있나요? (acmicpc.net)

글 읽기 - 26%에서 틀렸다고 나옵니다. 혹시 반례를 알려주실 수 있나요?

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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 count = 0;
		
		count = (V-B)/(A-B);
		
		if((V-B)%(A-B) != 0) {
			count++;
		}
		System.out.println(count);
	}
}

결국은 요렇게 풀었는디...

왜 이진탐색으로 안 되는 거지 ?!?!?!