[백순코] 1699번 - 제곱수의 합(13위)

flaxinger·2021년 7월 6일
0

개인적인 문제 풀이 이후 타인의 코드를 참고했습니다.

문제 링크

Naive 풀이

다음은 백준의 1699번(실버 3) 문제에 대한 naive 코드이다. 문제는 자연수 N이 주어졌을 때 이를 자연수 제곱으로 표현한다면 이에 필요한 최소 항의 수를 구하는 것이다. 전형적인 DP(Dynamic Programming) 문제이지만 아직은 익숙하지 않아 아래 코드를 보면 스파게티가 먹고 싶어지는 효과가 있다.

#include <bits/stdc++.h>
using namespace std;


int dp[100000];

void solve(int target){

    vector<int> v;
    int start, temp;
    int i = 0;
    int count = 0;
    int best = 100000;

    while(i*i <= target){
        v.push_back(i*i);
        i++;
    }

    bool cont = false;
    i--;
    start = i;
    while(i > 0){
        
        temp = target;
        count += temp/v[i];
        if(temp/v[i] > 0 && temp == target) start = i;
        temp = temp%v[i];
        if(dp[temp]==0) solve(temp);
        
        if(temp>0)count += dp[temp];       
        temp = 0;
        i--;
  
        if(count < best) best = count;
      
        count = 0;
    }

    if(best==100000) dp[target] = 0;
    else dp[target] = best;
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int target;
    cin >> target;

    dp[1] = 1;

    solve(target);

    cout << dp[target];
}

흔히, 피보나치 및 몇개의 정해진 작업(operation)의 조합으로 특정 결과를 도출할 때 최적의 조합을 찾는 문제들이 DP의 상징적인 문제들이다.(백준: 피보나치 함수, 백준: 1로 만들기) 이는 필요한 함수가 재귀적으로, 혹은 반복적으로 도는 경향이 있는데, 이때 반복적인 작업을 최소화 하기 위해 사용된다.

위의 코드를 보면 우선 N의 최대값인 100,001 길이의 배열을 초기화해주고, solve()함수가 끝날 때마다 주어진 dp에 결과값을 저장한다. 이때 매번 벡터에 각 수의 제곱을 저장해주고 이를 모두 확인하며 최소값을 구한다. 부합하는 하나의 제곱수를 확인하면, 동일하게 solve()함수를 통해 최적의 조합을 구해 이를 더해주고, 이미 구했다면 저장된 값을 사용한다(DP).

효율적인 코드

그럼 이제 스파게티를 플레이팅할 차례다. 최종코드는 아래와 같다.

#include <bits/stdc++.h>
using namespace std;

int dp[100000];
int v[350];

int solve(int target){

    int temp, stop, count;
    int i = 0;
    int best = 100000;


    while(i*i <= target) i++;
    i--;
    stop = i/5 *3;
    while(i > stop){
        count = 0;

        if(target/v[i] > 0){
            temp = target%v[i];
            if(dp[temp]==0) count = target/v[i] + solve(temp);  
            else count = target/v[i]+dp[temp];
            if(count < best) best = count;
        } 
        i--;
    }

    if(target!=0) dp[target] = best;
    return dp[target];
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int target, i = 0;
    cin >> target;

    while(i*i <= target){
        v[i]=i*i;
        i++;
    }

    dp[1] = 1;

    cout << solve(target);
}

스파게티 코드를 보면, 우선 상당히 메모리 비효율적인 부분이 많은 것을 알 수 있다. 따라서 조금의 정리와, 아래의 업그레이드를 추가하였다.

  • 제곱수 배열 vector -> array
  • 조건문 간소화
  • 반복문 최적화

여기서 꿀팁은, 반복문 최소화인데 최적의 조합을 구하기 위해 모든 경우의 수를 확인할 필요가 없다. 특정 임계치 이하의 조합은 최적일 수가 없기 때문이다(극단적인 예로 N이 10일 때 2제곱 이하의 조합으로 최적을 만들 수 있을 리 없다). 따라서 최대 i의 3/5 지점을 임계점으로 잡아두면 많은 시간을 아낄 수 있다. 이렇게만 바꾸어줘도 실행시간이 12ms에서 0ms대로 내려간 것을 확인할 수 있다.

여기서 메모리가 2412KB인데, 다른 순위권 코드는 보다 적은 메모리를 사용하는 것을 확인할 수 있다. 이는 dp때문에 100,000크기의 배열을 사용해서 그런 것인데, 빡센(?) 코딩을 한 몇몇 풀이 외에 아래 코드가 인상적이었다.
3중 for loop으로 DP없이 해결한 케이스인데, 향후 이에 대한 해설을 추가할 예정이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    int mn = 4;
    for (int i = 0; i * i <= N; ++i) {
        for (int j = i; i * i + j * j <= N; ++j) {
            for (int k = j; i * i + j * j + k * k <= N; ++k) {
                if (i * i + j * j + k * k == N) {
                    mn = 3 - (!i + !j + !k);
                    break; 
                }
            }
            if (mn != 4)
                break;
        }
        if (mn != 4)
            break;
    }
    cout << mn;
    return 0;
}
profile
부족해도 부지런히

0개의 댓글