16561번 3의 배수

2018년 서강대학교 프로그래밍 콘테스트(Mater) A번 문제

대회 : https://www.acmicpc.net/category/detail/1961

문제 : https://www.acmicpc.net/problem/16561

처음에 백트래킹으로 풀었는데, '시간 초과'가 났다.

그래서, 백트래킹 코드로 몇 개의 예제들을 입력하여, 추론하여 풀었다.

9 -> 1개
12 -> 3개
15 -> 6개
18 -> 10개
21 -> 15개
24 -> 21개
27 -> 28개

<백트래킹, 시간초과>

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int N = 0, result = 0;
 
void BackTracking(vector<int> vc)
{
    if (vc.size() == 3)
    {
        int sum = 0;
 
        for (int i = 0; i < 3; i++)
        {
            sum += vc.at(i);
        }
 
        if (sum == N)
        {
            ++result;
        }
 
        return;
    }
 
    for (int i = 3; i <= N; i++)
    {
        if (i % 3 != 0) continue;
 
        vc.push_back(i);
 
        BackTracking(vc);
 
        vc.pop_back();
    }
}
 
int main(void)
{
    scanf("%d", &N);
 
    vector<int> v;
 
    BackTracking(v);
 
    printf("%d\n", result);
 
    return 0;
}

정답 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int main(void)
{
    int n = 0;
 
    scanf("%d", &n);
 
    n = n / 3 - 2;
 
    printf("%d\n", n*(n + 1) / 2);
 
    return 0;
}