본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

달팽이는 올라가고 싶다 문제 풀이 해설 C, C++, 자바 [백준 2869번, COCI 2010/2011 기출문제]

반응형

안녕하세요. 정말 오랜만에 찾아온 알고리즘 풀이네요~

 

출처1: COCI 2010/2011 Contest2 hsin.hr/coci/archive/2010_2011/

출처2: 백준 기본수학1 2869번 문제

정답률: 26.44%

난이도: 하

[2869번] 달팽이는 올라가고 싶다

문제

[해석본]

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

 

입출력

입력:

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

 

출력:

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

 

풀어봅시다~~~

 

ANSWER 문제풀이~!

사진출처: https://ywc.thehindu.com/articles/snail-trail/

문제를 보자마자 무슨 문젠지 바로 감오셨죠??

대한민국 정규 수학 교과 과정에 툭하면 나오는 달팽이문제....

그걸 소스코드로 풀라는 거~~~

 

첫 날~ A만큼 올라갔는대 높이(V)가 A보다 작다! 그럼 day는 1이 되고 문제는 끝이 나겠죠?

근데 만약 벽 높이가 A보다 커요, 그러면 밤이 찾아올거고 B만큼 미끄러질거예요~~~

그럼 다음날이 되고 (day++) 

다시 달팽이는 벽을 기어가겠죠....  어제 최종 위치에서 + A만큼 기어가고 이게 V보다 크면 day 2에서 멈추고 작으면 다시 미끄러질거예요..

 

간단하죵??! 차근 차근 일련의 과정을 소스로 표현해볼까요?

 

[JAVA 문제 풀이 - 오답]

이번엔 자바 언어로 먼저 풀어볼까요~

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

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 up = Integer.parseInt(st.nextToken());
		int down = Integer.parseInt(st.nextToken());
		int height = Integer.parseInt(st.nextToken());
		int result = 0, day = 1;
		for( ; result + up < height ; day++)
		{
			result += (up - down);
		}
		System.out.println(day);
	}
}

이렇게 했더니 시간초과가 나왔네.. 

처음부터 시간초과;;

반복문을 써서 그런것 같네요. 왠지 문제가 넘나 쉽더라..

시간복잡도를 줄이기 위해 반복문도 수학으로 바꿔서 변경해봅시다. 

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

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 up = Integer.parseInt(st.nextToken());
		int down = Integer.parseInt(st.nextToken());
		int height = Integer.parseInt(st.nextToken());			
		System.out.println((height-up)%(up-down)==0? \
        		(height - up) / (up - down) +1 : (height - up) / (up - down) +2);
	}
}

 

첫째날 0 + up < height? 

둘째날 0 + (up - down) + up < height? 

n째날,, 0 + (n-1)(up-down) + up < height

 

하루동안 움직인 움직인 거리는 (up -down)

n 번째 날 어제(n-1)이 지난 최종 위치는 (n-1)(up-down)이라는 뜻이겠죠?

즉 (n-1)(up-down) + up >= height를 만족하는 최소 정수 n값을 구하는 문제예요.

 

[C언어 문제풀이]

#include <stdio.h>
#include <math.h>
int main()
{
	int up, down, height;
	scanf("%d %d %d", &up, &down, &height);
	printf("%.lf\n", ceil((double)(height - down) / (up - down)));
	return 0;
}

C언어는 포맷지정자로 쪼개 입력받을 수 있으니 일일이 쪼개줘야 하는 자바보다는 당연히 소스코드 양은 줄겠죠~

 

이번에는 같은 문제 풀인데 약간 사고방식을 틀어봤어요.

하루에 올라가는 거리는 (up - down)이 되겠죠? 

그러면 n day * (up - down)이 벽의 길이보다 높으면 되는거 아닌가요?! 할 수 있는데..! 

밤에 미끄러지기 전의 결과가 벽 길이보다 높아도!!! 통과라는걸 고려해줘야 합니다.

즉 n day * (up - down) > height - down 이 되는 n의 값을 구하면 되는겁니다.

근데 이렇게 하면 우항이 소수가 나오면 n은 정수라서 우항 올림한 정수 값이 답이 되어야 합니다.

 

[C++언어 문제풀이]

#include <iostream>
using namespace std;
int main()
{
	int up, down, height;
	cin >> up >> down >> height;
	cout << (int) (height - down -1) / (up - down) + 1;
	return 0;
}

똑같은 문젠데요. 실수가 나오는데 올림같은 별도의 함수를 이용해서 풀기 싫다! 

if문으로 나눠떨어지는지 굳이 분기하기도 귀찮다! 그럴 때 쓸 수 있는 방법입니다.

(height - down)에다가 미리 1을 빼놓고 몫에 1을 더하는 방식으로 정수화시킨 거예요.

 

오늘은 여기까지입니다~! 도움이 되셨다면 공감 :) 

다음 포스팅에서 봐요

반응형