[코드트리] 제곱수의 합으로 나타내기

2024. 12. 8. 16:13·PS

 

 


 

문제

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

 

 

개념

DP

 

 

실행 결과

 

 

 

 

 

구현 코드(c++)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int sol(int n) {
  vector<int> dp(n + 1, 5000);
  dp[0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j * j <= i; ++j) {
      dp[i] = min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
}

int main() {
  int n;
  cin >> n;
  cout << sol(n) << endl;
  return 0;
}

 

 

 

 

코드 설명

최소 개수의 제곱수 합으로 표현하기 위한 최소 제곱수의 수를 저장하는 dp 배열을 선언한다.

최소 제곱수를 계산해야하므로 문제에서 최대 범위로 주어진 5000으로 초기화한다.

j를 각 제곱수라고 하면, j를 제곱하여 i보다 작거나 같은 모든 경우의 수를 고려한다. 
이때 j가 0일때는 0이므로 제외하고 1부터 2,3.. 하나씩 수를 늘려가며 조건을 만족할 때까지 최소 개수를 구한다.

예를 들어 i = 12라면 

dp[12 - 1^2] + 1 = dp[11] + 1
dp[12 - 2^2] + 1 = dp[8] + 1
dp[12 - 3^2] + 1 = dp[3] + 1 

따라서 최솟값은 dp[12] = 3이다.

 

 

 

 


 

저작자표시 (새창열림)

'PS' 카테고리의 다른 글

[백준] 9935번: 문자열 폭발  (0) 2024.12.22
[백준] 2667번: 단지번호붙이기  (0) 2024.12.13
[백준] 1010번: 다리 놓기  (0) 2024.10.23
[백준] Fly me to the Alpha Centauri  (0) 2024.10.17
[프로그래머스] 타겟 넘버  (0) 2024.10.12
'PS' 카테고리의 다른 글
  • [백준] 9935번: 문자열 폭발
  • [백준] 2667번: 단지번호붙이기
  • [백준] 1010번: 다리 놓기
  • [백준] Fly me to the Alpha Centauri
abyss-s
abyss-s
프론트엔드 개발합니다!
  • abyss-s
    abyss-s의 블로그입니다.
    abyss-s
  • 전체
    오늘
    어제
    • 분류 전체보기 (189)
      • Web (16)
        • JavaScript (6)
        • TypeScript (1)
        • React (5)
        • Vue (0)
        • Storybook (1)
        • Next.js (1)
      • Backend & Infra (8)
        • Database (3)
        • Node.js (2)
        • SpringBoot (1)
      • PS (71)
      • CS (30)
        • OS (13)
        • Structure & Algorithm (5)
        • Network (10)
        • 정보처리기사 (2)
      • Language (18)
        • OOP (1)
        • JAVA (13)
        • C++ (4)
      • Activities (13)
        • 멋쟁이 사자처럼 (2)
        • OSSCA (3)
        • LG U+ URECA (4)
        • Project (2)
      • AI (0)
      • Git & Github (5)
      • Notion (1)
      • IT (4)
      • Statistics (11)
      • Book (4)
      • Diary (1)
      • Game (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • 깃허브
    • 백준
    • 트위터
  • 공지사항

    • abyss-s의 티스토리에 오신 것을 환영합니다.
  • 인기 글

  • 태그

    운영체제
    그리디
    통계학
    C++
    코드트리
    백준
    자바기반응용프로그래밍
    JavaScript
    BFS
    파이썬
    React
    Java
    DP
    네트워크
    OS
    자바스크립트
    BAEKJOON
    생활코딩
    Python
    github
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
abyss-s
[코드트리] 제곱수의 합으로 나타내기
상단으로

티스토리툴바