2839번: 설탕 배달
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그
www.acmicpc.net
작성 코드 (.py)
import sys
sys.stdin = open("input.txt", "r") # 제거
input = sys.stdin.readline
def solution(n):
if n == 3:
return print(1)
elif n == 4:
return print(-1)
table = [-1] * (n + 1)
table[3], table[5] = 1, 1
for i in range(6, n + 1):
if table[i - 3] == -1 and table[i - 5] == -1:
table[i] = -1
elif table[i - 3] == -1 or table[i - 5] == -1:
table[i] = max(table[i - 3], table[i - 5]) + 1
else:
table[i] = min(table[i - 3], table[i - 5]) + 1
return print(table[n])
solution(int(input()))작성 코드 (.js)
function solution(n) {
if (n === 3) return 1;
if (n === 4) return -1;
const table = Array(n + 1).fill(-1);
[table[3], table[5]] = [1, 1];
for (let i = 6; i <= n; i += 1) {
if (table[i - 3] === -1 && table[i - 5] === -1) table[i] = -1;
else if (table[i - 3] === -1 || table[i - 5] === -1)
table[i] = Math.max(table[i - 3], table[i - 5]) + 1;
else table[i] = Math.min(table[i - 3], table[i - 5]) + 1;
}
return table[n];
}
구현 로직 (DP)
여러가지 방법이 있겠지만 DP 테이블을 만들어 해결합니다. 점화식은 다음과 같습니다.
a[i] = min(a[i - 3], a[i - 5]) + 1 { 단, a[i - 3]또는 a[i - 5] 킬로그램을 배달할 수 없는 경우 제한사항 적용 }
DP테이블에서 매 i 킬로그램(index)에서 봉지를 가져가는 횟수는 3킬로 봉지를 사용한 경우와 5킬로 봉지를 사용한 경우중 더 적은 횟수 + 1을 적용하지만 만약 두 경우 모두 배달 불가능한 무게였다면 i 킬로그램 역시 배달이 불가능하며, 두 경우 중 한쪽만 배달 가능한 무게라면 가능한 무게 케이스에서의 횟수 + 1을 적용합니다.
1. n길이의 테이블 생성
2. 현재 들어온 무게에서 -3과 -5 무게의 경우 중 더 적은 무게의 봉지 수 + 1 적용
3. -3과 -5 무게 모두 배달 불가능하다면(-1) 현재 들어온 무게도 불가능 처리
4. -3과 -5 무게 중 한쪽만 가능하다면 가능한 무게의 봉지 수 + 1 적용