[백준][C++] 17626 Four Squares

17626. Four Squares

17626번: Four Squares

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

참신하고 재미있었던 문제!

자연수를 넷 이하의 제곱수의 합으로 표현할 수 있는 게 신기했다.

 

제곱수를 한 배열에 모으고, DFS를 이용해 탐색했다.

 

알고리즘 설계

1. 1부터 N까지의 제곱수를 벡터에 모은다.
2. 모은 제곱수를 내림차순으로 DFS를 돌려준다!
3. 제곱의 합이 내림차순으로 돌리는 이유는 대부분 큰 값으로 먼저 구성되기 때문!
4. 현재 값 + 추가할 값 > N이거나 현재 값 + 추가할 값 * 남은 횟수 < N이라면  N보다 크거나 N과 같아질 수 없는 크기라면, 탐색할 이유가 없으므로 재귀를 돌려주지 않는다.
5. count가 4가 되거나, 그 전에 N을 만들었다면 재귀를 빠져나온다.

 

코드로 구현해보았다.

DFS

void DFS(int curNum = 0, int count = 4)
{
    if (curNum == target)
    {
        answer = min(answer, 4 - count);
        return;
    }

    if (count == 0) return;

    for (int i = sNumbers.size() - 1; i >= 0; i--)
    {
        // 합쳤을 때 타겟의 크기를 넘거나
        // count만큼 곱한 값을 합쳐도 target이 넘지 못할 때는
        // 재귀를 돌리지 않는다!
        if (curNum + sNumbers[i] > target || curNum + sNumbers[i] * count < target)
        {
            continue;
        }

        DFS(curNum + sNumbers[i], count - 1);
    }
}

main

int main()
{
    cin >> target;

    // 제곱수 모아주기
    for (int i = 1; i <= sqrt(50000); i++)
    {
        if (i * i > target) break;
        sNumbers.push_back(i * i);
    }

    DFS();

    cout << answer;
}

 

처음엔, N보다 큰 부분만 재귀를 돌려주지 않았다가, 시간 초과가 났다.

 

곰곰히 생각해보니, 큰 수가 들어온다면 작은 제곱수들이 많은 시간을 잡아먹을 것 같아서 재귀를 돌리는 걸 빼주었더니 시간 초과가 나지 않았다.

 

제곱수를 저장하는 부분이 DP 문제와 어울리는 풀이법 같다. 재미있었던 문제!