백준알고리즘 2869번 달팽이는 올라가고 싶다 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 2869
• 문제명: 달팽이는 올라가고 싶다
• 언어: C#
• 분류: 수학
• 비고: 

 

문제

There is a snail on the ground. It wants to climb to the top of a wooden pole with the height of V meters, measuring from the ground level. In one day it can climb A meters upwards, however during each night it sleeps, sliding B meters back down. Determine the number of days it needs to climb to the top. 

 

입력

The first and only line of input contains three integers separated by a single space: A, B, and V (1 ≤ B < A ≤ V ≤ 1 000 000 000), with meanings described above. 

 

출력

The first and only line of output must contain the number of days that the snail needs to reach the top.

 

풀이

반복문을 사용하기 보다는 int day = 에 있는 공식을 상식으로 알아두는 것이 좋다.

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

// 낮에 올라가는 높이, 밤에 미끄러지는 높이, 나무 막대의 전체 높이를 입력한다
int[] abv = sr.ReadLine().Split().Select(int.Parse).ToArray();
// 나무 막대 맨 위까지 올라가는데 걸리는 날
// (전체 높이 - 미끄러지는 높이 - 1) / (올라가는 높이 - 미끄러지는 높이) + 1
int day = (abv[2] -  abv[1] - 1) / (abv[0] - abv[1]) + 1;

sw.WriteLine(day);

sr.Close();
sw.Close();

 

후기

처음에는 이 문제를 반복문으로 풀어 보았다. 정답은 나왔지만 제출하면 시간 초과라는 결과만 나왔다. 그렇게 20분을 보내고 피드백을 통해 깨달은 것은 이러한 문제는 Stream을 사용해도 반복문을 사용하면 0.25초 이내로 풀 수 없는 문제였다. 위의 공식을 이해할 수 있다면 좋겠지만 급한 사람이라면 상식으로 알아두는 것이 도움이 될 것이다.

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

int[] abv = sr.ReadLine().Split().Select(int.Parse).ToArray();

int day = 0;
int snailPos = 0;

while(snailPos < abv[2])
{
    snailPos += abv[0];
    if(snailPos < abv[2])
        snailPos -= abv[1];
    day++;
}

sw.Write(day);

sr.Close();
sw.Close();

 

이게 시간 초과가 났던 코드다. While 반복문을 사용한 것이 시간 초과의 원인이었다. 처음에는 int[] abv = sr.ReadLine().Split().Select(int.Parse).ToArray(); 문을 사용한 것이 원인이라고 생각했다. 디버깅을 했을 3~4초라는 숫자를 보고 이렇게 생각했지만 정답에서는 이런 식으로 입력받고도 문제가 없었다. 반복문은 O(N)만큼의 시간 복잡도를 가진다. 그러니 반복문을 많이 쓸 수록 소요 시간이 늘어난다.