1. 오늘의 학습 키워드
- 그리디 알고리즘
2. 문제: 설탕 배달 (2839번)
- 단계: 🥈 실버 4단계
- 출처: www.acmicpc.net
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 345432 | 132166 | 98349 | 37.687% |
문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
예제 입력 1 복사
18
예제 출력 1 복사
4
예제 입력 2 복사
4
예제 출력 2 복사
-1
예제 입력 3 복사
6
예제 출력 3 복사
2
예제 입력 4 복사
9
예제 출력 4 복사
3
예제 입력 5 복사
11
예제 출력 5 복사
3
출처
Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 1번
알고리즘 분류
3. 나의 풀이
문제 풀이 및 접근
이 문제는 3kg 봉지와 5kg 봉지를 사용하여 정확히 Nkg의 설탕을 배달하는 문제입니다. 상근이는 가능한 한 적은 개수의 봉지를 사용하고자 합니다. 이때 정확히 Nkg을 만들 수 없는 경우에는 -1을 반환해야 합니다.
접근 방법
문제를 해결할 수 있는 두 가지 주요 접근 방법은 그리디 알고리즘과 동적 프로그래밍(DP)입니다.
3-1. 그리디 알고리즘 풀이
그리디 알고리즘은 매 순간 최적의 선택을 하여 문제를 해결하는 방식입니다. 이 문제에서는 5kg 봉지를 우선적으로 사용하는 것이 최적의 선택입니다. 그 이유는 더 큰 봉지를 사용하면 남은 설탕의 양이 줄어들기 때문입니다. 만약 5kg 봉지로 나누어 떨어지지 않는다면, 3kg 봉지를 하나씩 추가하며 가능한 최소 봉지 수를 찾습니다.
코드 설명
def sugar_delivery_greedy(N):
cnt = 0 # 봉지 개수 카운터
while N >= 0: # N이 0 이상일 때까지 반복
if N % 5 == 0: # 5로 나누어떨어지면
cnt += N // 5 # 5kg 봉지 개수를 추가
return cnt # 결과 출력
else:
N -= 3 # 3kg 봉지를 하나 추가하고 N에서 3을 뺌
cnt += 1
return -1 # 정확하게 만들 수 없는 경우 -1 반환
풀이 과정
N이 5로 나누어떨어지면, 5kg 봉지로만 나눌 수 있으므로 그 개수를 바로 반환합니다.- 그렇지 않다면, 3kg 봉지를 하나씩 추가하며
N에서 3을 계속 빼줍니다. - 만약
N이 0보다 작아지면, 정확히Nkg을 만들 수 없으므로1을 반환합니다.
시간 복잡도
이 방법은 N을 3씩 줄이면서 5로 나누어떨어질 때까지 반복하기 때문에, 시간 복잡도는 → 입니다. 매우 빠르게 답을 구할 수 있습니다.
3-2. 동적 프로그래밍(DP) 풀이
동적 프로그래밍은 작은 문제들을 해결하면서 그 결과를 저장하고, 이를 이용해 더 큰 문제를 해결하는 방법입니다. 이 문제에서는 각 무게 i에 대해 최소 봉지 개수를 저장해나가는 방식으로 해결할 수 있습니다.
코드 설명
def sugar_delivery_dp(N):
INF = 5001 # 매우 큰 값 설정 (최대 5000kg까지 가능하므로 5001 이상이면 불가능한 경우)
dp = [INF] * (N + 1) # dp 배열을 INF로 초기화
dp[0] = 0 # 0kg은 0개의 봉지가 필요함
# 동적 프로그래밍으로 dp 테이블 채우기
for i in range(3, N + 1):
if i >= 3:
dp[i] = min(dp[i], dp[i - 3] + 1)
if i >= 5:
dp[i] = min(dp[i], dp[i - 5] + 1)
# dp[N]이 여전히 INF이면 Nkg을 만들 수 없다는 의미
return dp[N] if dp[N] != INF else -1
풀이 과정
dp[i]는ikg을 만들기 위한 최소 봉지 개수를 의미합니다. 처음에는 모든 값을 매우 큰 값으로 초기화합니다. 0kg을 만들기 위해서는 봉지가 필요 없으므로dp[0] = 0으로 설정합니다.- 3kg와 5kg 봉지를 각각 사용할 수 있는 경우에 대해 최소 봉지 개수를 갱신해 나갑니다.
- 최종적으로
dp[N]값이INF가 아니라면,Nkg을 만들 수 있는 최소 봉지 개수를 반환합니다. 그렇지 않으면1을 반환합니다.
시간 복잡도
동적 프로그래밍 방식은 N까지의 값을 모두 계산하므로, 시간 복잡도는 입니다. 하지만 N의 최대값이 5000이므로, 충분히 효율적으로 동작합니다.
두 가지 방식 비교
- 그리디 알고리즘:
- 장점: 매우 직관적이며, 빠르게 해결할 수 있습니다.
- 단점: 그리디 알고리즘이 항상 최적해를 보장하지는 않지만, 이 문제에서는 최적의 해를 보장합니다.
- 동적 프로그래밍:
- 장점: 더 일반적인 문제 해결 방식이며, 최적해를 보장합니다.
- 단점: 코드가 복잡해지며, 그리디 방식보다 계산이 많습니다.
두 방식 모두 정확한 답을 찾을 수 있지만, 이 문제의 경우 그리디 알고리즘이 더 직관적이고 빠른 풀이 방법입니다.
하지만 저는 공부!를 하고 코테 실력 향상을 위해 다 풀어보았습니다.
전체 코드
######################## greedy ################
import sys
N = int(sys.stdin.readline().strip())
def sugar_delivery_greedy(N):
cnt = 0
while N >= 0:
if N % 5 == 0:
cnt += N // 5
return cnt
else:
N -= 3
cnt += 1
return -1
print(sugar_delivery_greedy(N))
######################## greedy ################
#################### Dynamic Programming ##########################
import sys
def sugar_delivery_dp(N):
INF = 5001 # 큰 값으로 설정 (최대 5000kg까지 가능하므로 5001 이상이면 불가능한 경우)
dp = [INF] * (N + 1)
dp[0] = 0 # 0kg은 0개의 봉지가 필요함
# 동적 프로그래밍으로 dp 테이블 채우기
for i in range(3, N + 1):
if i >= 3:
dp[i] = min(dp[i], dp[i - 3] + 1)
if i >= 5:
dp[i] = min(dp[i], dp[i - 5] + 1)
# dp[N]이 여전히 INF이면 Nkg을 만들 수 없다는 의미
return dp[N] if dp[N] != INF else -1
# 입력 처리
N = int(sys.stdin.readline().strip())
# 결과 출력
print(sugar_delivery_dp(N))
#################### Dynamic Programming ##########################마무리
이번 문제는 그리디 알고리즘과 동적 프로그래밍(DP) 두 가지 방법으로 풀 수 있는 문제였습니다. 설탕 봉지를 최소 개수로 배달하는 이 문제는 그리디 알고리즘을 사용하면 매우 직관적이고 효율적으로 해결할 수 있습니다. 하지만 동적 프로그래밍 방식으로도 문제를 해결할 수 있었으며, 이를 통해 더 복잡한 문제를 다루는 방법을 연습할 수 있었습니다.
그리디 알고리즘은 즉각적인 최적의 선택을 해야 할 때 매우 효과적이고 빠르며, 동적 프로그래밍은 여러 경우의 수를 모두 고려해 최적의 해를 보장하는 일반적인 방법입니다.
어떤 문제는 그리디나 DP로만 풀 수 있고, 어떤 문제는 둘 다 풀 수 있는 경우가 있습니다. 요약하자면 다음과 같이 할 수 있습니다.
- 일부 그리디 문제는 동적 프로그래밍으로 풀 수 있지만, 그 반대는 항상 성립하지 않습니다. 그리디 알고리즘은 빠르고 간단하지만, 최적 부분 구조나 중복 부분 문제 같은 DP의 특성을 사용하지 않기 때문에, 모든 그리디 알고리즘 문제를 동적 프로그래밍으로 풀 수 있는 것은 아닙니다.
- 또한, 그리디 알고리즘이 항상 최적해를 보장하지는 않기 때문에, 그리디로 풀 수 없는 문제들은 동적 프로그래밍을 통해 더 정확하게 풀어야 할 때가 많습니다.
실제 코딩 테스트에서는 다양한 문제 유형에 맞춰서 그리디와 동적 프로그래밍을 적절히 사용하는 능력을 기르는 것이 중요합니다.
아직 코린이지만 초반에 알고리즘 유형을 풀 때 가장 많이 풀고 먼저 풀어야 하는것이 그리디, 탐색, DP입니다. 왜냐하면 기출 빈도가 가장 높기 때문입니다. 그래서 저도 자료 구조 유형과 그리디를 먼저 시작하고 있습니다.
이번 문제를 통해 두 방법의 차이와 각각의 장점을 이해할 수 있는 좋은 기회가 되었습니다.
더 나은 개발자가 될거야!!💪
