알고리즘 선택 트랙 [2일차]

1. 설탕배달

 

<문제>

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

 

<해설>

(1) 알고리즘이란?

1. 설탕 입력을 받는다.

2. 기본적으로 해당 설탕을 3개씩 봉지에 담는다.

3. (1) 만약 설탕의 갯수가 5의 배수라면 5개씩 봉지에 담는다.

3. (2) 만약 설탕의 갯수가 5의 배수가 아니라면 3개씩 봉지에 담는다.

4. 2.~4.사이의 과정을 주어진 설탕이 0보다 클 때까지 반복한다.

5. 만약 남는 설탕의 갯수가 0보다 작으면 -1을 리턴한다.

(2) 자료구조및 구현?

 

사용할 자료구조는 없다.

작업한 코드는 다음과 같다.

# input = int(input())

# cnt = 0

 

# while input > 0:

# if input % 5 == 0:

# cnt += input // 5

# input %= 5

# else:

# input -= 3

# cnt += 1

# if input < 0:

# cnt = -1

# print(cnt)

 

(3) 느낀점

이문제는 그리디 알고리즘 문제이다. 왜냐하면 문제를 최대한 간단한 방법으로 푸는 문제이기 때문이다. 하지만 기존에 문제와는 다르게 기본적으로 3개씩 묶는 봉지에 담는다는 차이가 있다. 그래서 이런 문제를 통해서 문제에 대한 생각의 폭을 넗여하겠다고 생각했다.

 

2. 달팽이는 올라가고 싶다

<문제>

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

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

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

<해설>

(1) 알고리즘이란?

1. A,B,V를 입력받는다.

2. V의 값을 마지막 밤을 제외한 거리로 제 정의 한다.

3. 하루동안 달팽이가 갈 수 있는 거리를 구한다.

4. V와 하루동안 달팽이가  갈 수 있는 거리를 이용해서 며칠이 걸렸는지와 남은 거리를 찾은다

5. -> 몫 : 며칠 , 나머지 : 남은 거리

(2) 자료구조와 구현이란?

사용한 자료구조는 없다.

#A,B,V

# V = V - B

# k = V % (A-B)

if k == 0:

print(v // (A-B))

else:

print(v // (A-B)) + 1

(3) 느낀점

처음에는 while 문을 통해서 위 문제를 해결하게 됬는데 하지만 시간초과가 나서 왜 시간 초과가 나는지 살펴보았다. 그리고 알고리즘에서 시간 초과가 나는 이유는 while문을 통해 반복하게 되면 O(k) 이다 따라서 이 문제를 해결하기 위해서 while 반복문 없이 코드를 작성했다.