본문 바로가기

Algorithm/Implementation

(C++) - 백준(BOJ) 16561번 : 3의 배수

반응형

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

 

16561번: 3의 배수

윤영이는 3의 배수 마니아이다. 그는 모든 자연수를 3개의 3의 배수의 자연수로 분해하는 것을 취미로 가지고 있다. 문득 그는 자신에게 주어진 수를 3개의 3의 배수로 분리하는 경우의 수가 몇 개인지 궁금해졌다. 하지만 윤영이는 마지막 학기이기 때문에 이런 계산을 하기에는 너무 게을러졌다. 그래서 당신에게 이 계산을 부탁했다. 즉, 임의의 3의 배수 자연수 n이 주어졌을 때, 해당 수를 3의 배수의 자연수 3개로 분리하는 방법의 개수를 출력해라. 단 분해

www.acmicpc.net

완전탐색 문제였습니다. 시간제한이 0.1초기 때문에 100만번 연산을 초과하면 시간초과가 납니다. 3개의 수를 결정하는데 for문을 3개를 사용한다면 1000 * 1000 * 1000 즉 10억번 연산하게 되어 10초가 걸리므로 시간초과입니다. 따라서 for문 2개로 답을 내야합니다. 2개만 결정하면 나머지 숫자는 자동으로 결정되므로 문제를 풀 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
//2개를 뽑으면 나머지 하나는 자동으로 결정된다.
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    int ans = 0;
    cin >> n;
    for (int i = 1; i <= n/3; i++)
    {
        for (int j = 1; j <= n/3; j++)
        {
            int sum = 0;
            sum = i * 3 + j * 3;
            if ((n-sum) % 3 == 0&& sum<n)
                ans++;
        }
    }
    cout << ans << '\n';
}