17626번: Four Squares

문제링크

C++

#include <iostream>

using namespace std;

int arr[50001];

void    find(int N)
{
    arr[0] = 0;
    arr[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        arr[i] = arr[i - 1] + 1;
        for (int j = 1; j * j <= i; j++)
        {
            if (arr[i] >= arr[i - j * j] + 1)
                arr[i] = arr[i - j * j] + 1;
        }
    }
    cout << arr[N] << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    find(N);
}

Python

import math
import sys
input = sys.stdin.readline

arr = [0] * 50001
N = int(input())
arr[1] = 1

for i in range (2, N + 1):
    arr[i] = arr[i - 1] + 1
    for j in range (1, int(math.sqrt(i))+1):
        if arr[i] > arr[i - j * j] + 1:
            # print(i, j)
            arr[i] = arr[i - j *  j] + 1
print(arr[N])

• 모든 제곱수는 한 개의 제곱수로 나타내어질 수 있다는 것을 파악하는 것이 관건이었다.
• $O(N^{3/2})$의 시간 복잡도로 풀었다. ($N * \sqrt{N}$?)
• 파이썬에서 기존 c에서와 같은 for문은 안 되므로 굳이 그런 형태를 원한다면 while문을 써야 하려나?
• Python3에서는 시간초과, pypy3에서는 통과했다. pypy에서는 그만큼 메모리를 더 많이 먹는다는 얘기가 있는 것 같다. 또 간혹 python3가 더 빠른 경우도 있다고 한다. 나중에 차이에 대해 조금 더 알아봐야할 것 같다.
• 실제 코딩테스트에서는 파이썬에 그만큼 시간 메리트를 더 준다고 하는데 그 득실이 얼만큼 되는지 나중에 알아보기. 물론 그 전에 조금 더 효율적인 알고리즘을 짜는 것이 필요하겠지만..
• 파이썬에 대해 그때그때 필요한 문법만 찾아보고 있는데 조금 효율적이지 못한 것 같다. 아무리 코테를 위한 파이썬이라지만 pythonic한 코드 작성을 위한 최소한의 공부가 필요하지 않나 싶다.