https://www.acmicpc.net/problem/1437
숫자 N을 0이 아닌 정수의 합으로 나타낼 수 있으며, 그 수들의 곱의 최댓값을 구하는 문제입니다.
우선 그 합을 이루는 정수는 N이 커질수록 답이 커질수밖에 없습니다.
그 기준은 5가 되겠습니다.
5 = 2 + 3이며, 2 * 3 = 6 > 5이기 때문이죠.
5보다 작은 수는 그 수 자체를 곱하는게 더 크다고 할 수 있습니다.
그렇다면 문제를 쉽게 해결할 수 있습니다.
N을 5보다 작은 어떤 수로 계속 빼면 답을 구할 수 있습니다.
그 수는 3이나 4가 될 수 있을텐데, 6 = 2 + 2 + 2 = 3 + 3의 경우를 보시면 3이 최대한 많이 들어가는 수가 크다는 것을 알 수 있습니다.
다른 수로 직접 구해보셔도 4보다는 3으로 나누는 것이 제일 이득입니다.
따라서 N < 5가 되기 전까지는 3을 계속 빼주도록 하고, 남은 5 미만의 N을 곱해주시면 됩니다.
|
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
|
#include <iostream>
#define MOD 10007
using namespace std;
int N;
void func() {
int ret = 1;
while (N >= 5) {
N -= 3;
ret = (ret * 3) % MOD;
}
cout << (ret * N) % MOD << '\n';
}
void input() {
cin >> N;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 2513 통학버스 (0) | 2024.07.14 |
|---|---|
| boj 15553 난로 (0) | 2024.07.13 |
| boj 23559 밥 (0) | 2024.07.11 |
| boj 2140 지뢰찾기 (0) | 2024.07.10 |
| boj 1132 합 (0) | 2024.07.08 |