16561.3의 배수

[문제]

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

즉, 임의의 3의 배수 자연수 n이 주어졌을 때, 해당 수를 3의 배수의 자연수 3개로 분리하는 방법의 개수를 출력해라. 단 분해한 수의 순서가 다르면 다른 방법으로 간주한다. 예를 들어 12 = 3 + 6 + 3 과 12 = 3 + 3 + 6 은 다른 방법이다.

 

[입력]

임의의 3의 배수 자연수 n이 주어진다. (3 ≤ n ≤ 3000)

 

[출력]

자연수 n을 분해하는 방법의 개수를 출력하라.

 

1.TC - Input

9

TC - output

1

2. TC - Input

12

TC - output 

3

 

[접근]

약 1일간 생각해 본 결과, 마땅히 구할 수 있는 방법을 찾지 못해, 원리 구글링.

1. 3개 for 문 사용시 time out

2. 2개의 3의 배수를 찾으면 나머지 하나는 정해진다. n - sum 을 진행하면 되기때문에, 이 결과가 0이 아니고 클 경우 count 증가, 0보다 작거나 같으면 3의 배수가 아니다.

 

[코드] - C++

#include<iostream>
using namespace std;
int N;
int Count;

int main()
{
    cin >> N;
    for(int i = 1; i < (N/3); ++i)
    {
        for(int j =1; j <(N/3); ++j)
        {
            if(N - ((3*i)+(3*j)) > 0)
                ++Count;
        }
    }
    cout << Count <<'\n';
    
    return 0;
}

[결과 및 시도]

[후기]

결과 및 시도가 2번 밖에 없었는데, 2일 이나 생각했다는건 그냥 원리 자체를 이해 못하고 손도 못댓다는 것이다.

구현력과 원리 이해도가 완전히 부족한 문제였다.

 

비슷한 조합론이나 이런문제 유형들을 보면서 다시 나오면 그때는 꼭 내 힘으로 풀어야겠다.