알고리즘/백준
[백준/C,C++] 16561번: 3의 배수
이민훈
2021. 4. 19. 01:35
16561번: 3의 배수
윤영이는 3의 배수 마니아이다. 그는 모든 자연수를 3개의 3의 배수의 자연수로 분해하는 것을 취미로 가지고 있다. 문득 그는 자신에게 주어진 수를 3개의 3의 배수로 분리하는 경우의 수가 몇
www.acmicpc.net
풀이
휴리스틱하게 작은 입력부터 출력을 계산해보다 보면 규칙이 나오는 문제입니다.
9 → 1개 / 3 + 3 + 3
12 → 3개 / 6 + 3 + 3, 3 + 6 + 3, 3 + 3 + 6
15 → 6개 / 9 + 3 + 3, 3 + 9 + 3, 3 + 3 + 9, 6 + 6 + 3, 6 + 3 + 6, 3 + 6 + 6
18 → 10개 / 12 + 3 + 3, 3 + 12 + 3, 3 + 3 + 12, ...
21 → 15개
24 → 21개
#include<iostream>
using namespace std;
int main(void)
{
int n; cin >> n;
n = n / 3 - 2;
int res = 0;
for (int i = 1; i <= n; i++) {
res += i;
}
cout << res;
return 0;
}반례
Input
3
Output
0
Input
30
Output
36
Input
3000
Output
498501