[Hackerrank] Sherlock and The Beast

https://www.hackerrank.com/challenges/sherlock-and-the-beast/problem

Sherlock and The Beast | HackerRank

 

void decentNumber(int n) {
    if(n < 3)
    {
        cout << -1 << endl;
        return;
    }
    
    if(n % 3 == 0)
    {
        cout << string(n , '5') << endl; 
        return;
    }
    
    int mod = n % 3;
    int q = n / 3;
    int numOf5 = 0;
    int numOf3 = 0;
    for(int i = q; i > 0; --i)
    {
        int tmp = n - (3 * i);
        if(tmp % 5 == 0)
        {
            numOf5 = 3 * i;
            numOf3 = tmp;
            
            string part5(numOf5, '5');
            string part3(numOf3, '3');
            cout << part5 + part3 << endl;
            return;
        }
    }    
    
    // n % 5 == 0
    if(n % 5 == 0)
    {
        cout << string(n, '3') << endl;
    }
    else 
    {
        cout << -1 << endl;
    }
}

 

길이가 주어지면 해당 길이에 맞는 Decent Number를 출력하는 것인데, 영어 해석이 잘 안돼서 이해하는 데 오래걸렸다..

내가 이해한 Decent Number의 조건은 다음과 같다.

1. 각 자리수는 무조건 3 또는 5로만 이루어진다. 3과 5가 같이 들어가도 된다.
2. 연속된 3의 개수는 5로 나누어 떨어져야 한다.
3. 연속된 5의 개수는 3으로 나누어 떨어져야 한다.
4. 위 조건을 만족하는 수 중 가장 큰 수여야 한다.

ex) 33333, 555, 55533333

33333의 길이(3의 개수)는 5이다. 5로 나누어 떨어지므로 decent number이다.

555의 길이(5의 개수)는 3이다. 3으로 나누어 떨어지므로 decent number이다.

55533333에서 555의 길이는 3으로 나누어 떨어지고, 33333의 길이도 5로 나누어 떨어지므로 decent number이다.

33333555는 55533333보다 작으므로 4번의 조건을 만족하지 않는다.

 

접근법

가장 간단한 케이스들부터 처리하면서 줄여나간다.

우선 길이가 3 미만이면 만들지 못하므로 -1을 출력하고 끝낸다.

decent number는 모두 5로 만드는 것이 가장 베스트이다. 따라서 입력받은 길이가 3으로 나누어 떨어지는 경우라면, 이 길이만큼 모두 5로 만들면 끝난다.

그 다음은 5와 3이 함께 나타날 수 있는 경우이다. 여기서도 가능한 5가 제일 많이 차지해야 한다. 그리고 5가 3보다 앞에 나와야 한다.

따라서 주어진 길이 n 중 가장 큰 3의 배수와 나머지 5의 배수의 조합이여야 한다. 예를 들어 14의 경우 9 + 5가 최선이다. 9는 3으로 나누어 떨어지므로 5를 사용할 수 있고 5는 5로 나누어 떨어지므로 3을 사용할 수 있다.

이 경우 5가 9개 3이 5개 연속으로 된 수가 정답이다. 이를 확인하기 위해선 길이 n을 여러 3의 배수로 나누어 보아야 한다. 그리고 그 나머지가 5로 나누어 떨어지면 된다. 3의 배수가 가장 커야하므로 가능한 가장 높은 3의 배수부터 확인한다. 그러려면 길이 n을 3으로 나눈 몫부터 시작하면 된다.

즉 길이가 14일 경우 3으로 나누면 몫은 4이다. 이때 3이 차지하는 길이는 12이지만 남은 길이 2가 5로 나누어 떨어지지 않으므로 조건을 만족하는 수를 만들 수 없다. 그러면 몫을 하나 줄여서 12보다 한 단계 작은 3*3 = 9로 시도해보는 것이다. 14에서 9를 빼면 5이고, 이는 5로 나누어 떨어지므로 최대한의 3의 배수를 사용한 결과가 된다.

만약 몫을 1까지 시도해보았는데도 안되면 그것은 3과 5가 조합될 수 없는 경우이다. 

n=5, 10, ... 등이 그러한 경우이다. 5로만 이루어질 수 있는 경우, 3과 5의 조합의 경우를 확인했으므로 3으로만 이루어질 수 있는 경우를 확인한다. 즉 5로 나누어 떨어지는 경우 길이만큼 모두 3으로 만들어서 출력한다.

그 외에는 모두 원하는 조건의 수를 만들 수 없는 경우이므로 -1을 출력하면 된다.