백준 2869번 달팽이는 올라가고 싶다.

보기에는 쉬운문제. 하지만 의외로 생각해야 할게 있었다.

일단 시작하는 날을 0부터가 아니라 1부터 인것. 그리고 낮에 올라가있는 위치와 밤에 올라가 있는 위치를 고려해야 한다.

 

처음 문제를 풀때는 단순하게 현재 달팽이의 위치와 나무의 높이를 비교했지만, 다르게 나왔고, 무엇이 문제 인지 고민했다.

달팽이가 올라가는 높이는 2, 떨어지는 높이는 1, 나무의 높이가 5라고 가정해보자.

 

1일차에는 2의 높이까지 올라와 있다. 하지만 나무의 높이가 5이므로 올라오지 못했다.

2일차에는 밤에 자는동안 1의 높이 만큼 떨어져 있다. 다시 올라가니 3의 높이 만큼 올라와 있다.

3일차에는 2의 높이에서 시작. 4만큼의 높이에 도착.

4일차에는 3의 높이에서 시작. 5만큼의 높이에 도착. 종료

 

이 문제의 핵심을 날짜를 추가하는 위치이다. 낮에 도착하지 못했더라면 day를 추가하고, 그리고 나서 다시 위치를 갱신해야한다. 

import java.util.Scanner;

public class Main {
	
	public int snail(int snailup,int snaildown,int treelength) {
		int day=1; //걸리는 시간
		int location=0; //달팽이 위치
		while(true) {
			location=location+snailup;
			if(location>=treelength)
				break;
			else {
				location=location-snaildown;
				day++;
			}
		}
		return day;
	}
	
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int snailup=scanner.nextInt(); //달팽이가 올라가는 거리
		int snaildown=scanner.nextInt(); //달팽이가 미끄지는 거리
		int treelength=scanner.nextInt(); //나무 높이
		Main problem=new Main();
		System.out.println(problem.snail(snailup,snaildown,treelength));
	}
}

출력결과 정답이지만, 시간제한에서 걸려버렸다. 나무의 높이가 커지면서 연산이 많이 져서 그런듯 하다. 시간복잡도를 계산해보자.

day=1,location=0 //2

location=location+snailup  //N번

if(location>=treelength) //N번

location=location-snaildown //N번

day++ //N번

4N+2 =O(N)

나무 높이가 1000000000일때 연산해야 하는 양도 그에따라 늘어버리니 시간초과가 떠버렸다. 가장 쉬운방법은 반복문을 줄이는 것. 혹은 수학적 공식으로 풀어버리는 것. 

 

수학적 공식으로 풀어보았다. 문제에 주어진 문자대로 수열을 만들었다. 달팽이의 위치에 대한 수열이다.

day1: A

day2: A-B+A=2A-B

day3: A-B+A-B+A=3A-2B

day4:A-B+A-B+A-B+A=4A-3B

가 성립한다. 이를 공식화 하면 

C(n)=nA-(n-1)B=nA-nB+B

이고 달팽이의 위치는 나무 높이보다 크거나 같아야 하므로 nA-nB+B>=V가 나온다.

A,B,V순서대로 5,1,6을 위 식에 대입해 보면

5n-n+1>=6

4n>=5

n>=5/4가 나오고 n의 값은 정수인 최솟값이 되야 하므로 2가 나온다. 정답이다.

 

위 식을 토대로 소스코드를 작성해보면

import java.util.Scanner;

public class Main {
	
	public int snail(int snailup,int snaildown,int treelength) {
		int day;
		day=snailup-snaildown;
		int right=treelength-snaildown;
		if((right%day)!=0) {
			return (right/day)+1;
		}
		else {
			return right/day;
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int snailup=scanner.nextInt(); //달팽이가 올라가는 거리
		int snaildown=scanner.nextInt(); //달팽이가 미끄지는 거리
		int treelength=scanner.nextInt(); //나무 높이
		
		Main problem=new Main();
		System.out.println(problem.snail(snailup,snaildown,treelength));
	}
}

근데 이렇게 해도 시간초과가 뜬다.... 작성함 함수 2개의 실행시간을 측정해서 조건에 적합한지 알아보기로 했다.

 

처음 작성했던 코드의 동작시간

문제에서 요구한 시간은 0.15초이다. 그러나 0.63초가 나왔기에 당연히 시간초과.

 

 

수학적으로 푼 코드의 동작시간

걸린시간은 0.001초가 나왔지만.... 왜 시간초과가 뜨는지 모르겠다. 아무튼 예제로 준 값을 입력한 결과 정답이기에 코드자체에는 문제가 없어보인다..