2839번: 설탕 배달
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그
www.acmicpc.net
설탕 Nkg을 3kg 봉지와 5kg 봉지로 담는 그리디 문제입니다.
봉지가 담을 수 있는 무게가 3, 5 kg으로 한정되어있으니 설탕의 무게는 (3의배수 + 5의배수) kg이 됩니다.
우선 5kg이 가장 크기때문에 N이 5로 나누어떨어지면 모든 설탕을 5kg에 담으면 됩니다.
그렇지 않으면 3kg씩 빼주면서 다시 N이 5로 나누어떨어지는지 확인하는 방식으로 구현하였습니다.
만약 위의 과정에서 N이 5보다 작고 3의배수가 아니면 -1을 출력해줍니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N;
static void func() {
int ans = 0;
while (true) {
if (N % 5 == 0) {
ans += (N / 5);
N = 0;
} else {
ans++;
N -= 3;
}
if (N == 0)
break;
if (N < 5 && N % 3 != 0) {
ans = -1;
break;
}
}
System.out.println(ans);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 8980 택배 (0) | 2021.02.16 |
|---|---|
| boj 11000 강의실 배정 (0) | 2021.02.16 |
| boj 1931 회의실 배정 (0) | 2021.02.16 |
| boj 11399 ATM (0) | 2021.01.29 |
| boj 1339 단어 수학 (0) | 2021.01.22 |