이 영역을 누르면 첫 페이지로 이동
포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

페이지 맨 위로 올라가기

포렌식 & 개발 이야기 - Forensics & Development

Pental - Forensics / iOS / Windows / Android / Kakaotalk / Telegram / Etc

[실버 2] 백준 1699 - 제곱수의 합 (파이썬)

  • 2025.04.13 12:04
  • Programming/백준
글 작성자: pental

https://www.acmicpc.net/problem/1699

풀이

자연수 N이 주어졌을 때, N을 제곱수들의 합으로 표현하는 데에 필요한 최소 항의 수를 구하는 문제이다.

예를 들어서 4 = 2 ^ 2 → 1개, 7 = 2 ^ 2 + 1 ^ 2 + 1 ^ 2 + 1 ^ 2 → 최소 4개

D[i]를 i의 제곱수의 합으로 나타낼 수 있는 최소 항의 수라고 생각하고 문제를 푼다.

점화식은 다음과 같다.

D[i] = min(D[i], 1 + D[i - j ^ 2])

if (i ** 0.5).is_integer():
    D[i] = 1
    continue

자기 자신 하나의 제곱수로 표현 가능한 경우는 바로 1로 설정하고 넘어간다.

D[i] = 1e9  # 초기값은 매우 큰 수
j = 1
while j * j <= i / 2:
    D[i] = min(D[i], 1 + D[i - j * j])
    j += 1

i보다 작은 모둔 제곱수 j ^ 2를 고려하면서, 1 + D[i - j ^ 2] , 즉 지금 j ^ 2 하나를 쓰고, 나머지 (i - j ^ 2)는 이미 계산된 값을 사용한다

j * j ≤ i / 2 조건을 속도 향상을 위한것인데, 사실은 그냥 i까지로 해도 맞는다.

코드

# 백준 1699 - 제곱수의 합
# 분류 : 다이나믹 프로그래밍

N = int(input())

D = [0] * (N + 1)

for i in range(1, N + 1) :
    if (i ** 0.5).is_integer() :
        D[i] = 1
        continue

    D[i] = 1e9
    j = 1
    while j * j <= i / 2 :
        D[i] = min(D[i], 1 + D[i - j * j])
        j += 1
print(D[N])
저작자표시 비영리

'Programming > 백준' 카테고리의 다른 글

[실버 1] 백준 1926 - 그림 (파이썬)  (0) 2025.04.14
[골드 5] 백준 1484 - 다이어트 (파이썬)  (1) 2025.04.13
[브론즈 2] 백준 1100 - 하얀 칸 (파이썬)  (0) 2025.04.12
[골드 4] 백준 9935 - 문자열 폭발 (파이썬)  (0) 2025.04.11
[브론즈 2] 백준 15829 - Hashing (파이썬)  (0) 2025.04.10

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [실버 1] 백준 1926 - 그림 (파이썬)

    [실버 1] 백준 1926 - 그림 (파이썬)

    2025.04.14
  • [골드 5] 백준 1484 - 다이어트 (파이썬)

    [골드 5] 백준 1484 - 다이어트 (파이썬)

    2025.04.13
  • [브론즈 2] 백준 1100 - 하얀 칸 (파이썬)

    [브론즈 2] 백준 1100 - 하얀 칸 (파이썬)

    2025.04.12
  • [골드 4] 백준 9935 - 문자열 폭발 (파이썬)

    [골드 4] 백준 9935 - 문자열 폭발 (파이썬)

    2025.04.11
다른 글 더 둘러보기

정보

포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

  • 포렌식 & 개발 이야기 - Forensics & Development의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

카테고리

  • Category (428) N
    • Forensics (103)
      • Magnet AXIOM (28)
      • Digital Forensics Informati.. (9)
      • Iphone Forensics (22)
      • DFC (7)
      • 디지털포렌식전문가2급 자격증 (10)
      • FTK ACE 자격증 (7)
    • 이것저것 (18)
      • Ubuntu (6)
      • 디스코드 봇 (4)
      • Volatility GUI (2)
    • CTF (32)
      • NEWSECU (14)
      • CTF-d (5)
      • Puzzel - Network Forensics (2)
      • Security Traps (2)
      • system32.kr (5)
      • HMCTF (4)
    • Programming (239) N
      • C (10)
      • Python (11)
      • 백준 (185) N
      • 프로그래머스 (32)
    • 그냥 개발 및 잡담 (16)
      • Docker (2)
      • Google Cloud (3)
      • OS 개발 (3)
    • Best of Best (20)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • 포렌식
  • 디지털포렌식
  • Forensics
  • pental
  • 프로그래머스
  • axiom
  • 파이썬
  • 백준
  • 전체 보기…

정보

pental의 포렌식 & 개발 이야기 - Forensics & Development

포렌식 & 개발 이야기 - Forensics & Development

pental

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © pental.

티스토리툴바