[TIL] 2025-11-28 | 본캠프 2일차 - Four Squares 풀이 및 조퇴

1. Day02

• Blueprint 라이브 세션 및 과제
• 개인 공부

2. 라이브 세션

• 언리얼 에디터 둘러보기
• Type==world 같은 명령어로 검색 필터
  

  

• 과제 (머티리얼을 수정해서 적용)
  

  

  
  

  

  3. 개인공부

• C++ 코딩테스트 완전정복 강의 (2-1, 2-2)
  • 알고리즘 효율성 및 필수문법 복습
• 실버3 17626번 Four Squares (다이나믹 프로그래밍) 오답
  • 처음에는 N 값을 2로 나눈다음 내려가면서 가장 큰 제곱수부터 빼기 방식으로 그리디하게 풀었으나 최소갯수가 아닌 반례가 존재함

// 실버3 17626번 Four Squares(다이나믹 프로그래밍)
#include <iostream>
#include <vector>

using namespace std;

vector<int> DP(50001, 0);

void P()
{
    DP[1] = 1;
    DP[2] = 2;
    DP[3] = 3;
    for (int i = 4; i <= 50000; i++)
    {
        int temp = i;

        for (int j = i / 2; j > 0; j--)
        {
            if (j * j <= temp)
            {
                if (temp > 3)
                {
                    temp -= j * j;
                    DP[i]++; 
                }
                else if(temp <= 3)
                {
                    if (temp == 3)
                    {
                        DP[i] += DP[3];
                    }
                    else if (temp == 2)
                    {
                        DP[i] += DP[2];
                    }
                    else if (temp == 1)
                    {
                        DP[i] += DP[1];
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
    }
}
int main()
{
    P();
    int N;
    cin >> N;
    cout << DP[N] << '\n';

    return 0;
}

• 점화식 jj ≤ i 일때 DP[i] = min(DP[i - jj] + 1) 을 사용하여 정리
  • i를 1부터 증가시키면서, 각 DP[i]를 구할 때
    1. j²(1², 2², 3², ...)을 작은 것부터 하나씩 선택한다
    2. 이미 계산해둔 DP[i - j²]에 1을 더한 값들을 비교한다
    3. 그 중 최솟값이 DP[i]가 된다

// 실버3 17626번 Four Squares(다이나믹 프로그래밍)
#include <iostream>
#include <vector>
#include <algorithm> // min()을 사용하기위해 추가

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    // min()로 최솟값 갱신을위해 1e9 == 충분히 큰 값으로 초기화
    vector<int> DP(N + 1, 1e9); 
    DP[0] = 0;

    for (int i = 1; i <= N; i++)
    {
        // j의 제곱이 i보다 작을때 까지 체크
        for (int j = 1; j * j <= i; j++)
        {    
            // i에서 제곱수 j²를 뺀 나머지의 최솟값(이미 계산됨)에 1을 더한 것들 중 가장 작은 값이 DP[i]
            DP[i] = min(DP[i], DP[i - j * j] + 1);
        }
    }
    cout << DP[N] << '\n';
    return 0;
}

4. 개인 사정으로 인한 조퇴 주말에 알고리즘 강의 및 문제 보충 필요

5. 다음주차 일정 : 라이브 세션 및 개인공부