[백준/Python] 17626번 Four Squares

2022. 7. 17. 10:23· Koala - 7기/코딩테스트 준비 스터디
목차
  1.  
  2. 문제 분석
  3.  
  4. 코드
  5. 문제 풀이

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

 

17626번: Four Squares

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1

www.acmicpc.net

 

문제 분석

모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 문제이다.

조건. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 1 ≤ n ≤ 50,000이다.

 

코드

 

다이나믹 프로그래밍

import math

n = int(input())
dp = [0,1]

for i in range(2, n+1):
    minValue = 1e9
    for j in range(1, int(math.sqrt(i)) + 1):
        minValue = min(minValue, dp[i - j**2])
    dp.append(minValue + 1)

print(dp[n])

 

브루트포스

import math

def fourSquares(n):
    # √n이 정수일 때
    if int(math.sqrt(n)) == math.sqrt(n):
        return 1
    # √(n - i^2)이 정수일 때
    for i in range(1, int(math.sqrt(n)) + 1):
        if int(math.sqrt(n - i**2)) == math.sqrt(n - i**2):
            return 2
    # √(n - i^2 - j^2)이 정수일 때
    for i in range(1, int(math.sqrt(n)) + 1):
        for j in range(1, int(math.sqrt(n - i**2)) + 1):
            if int(math.sqrt(n - i**2 - j**2)) == math.sqrt(n - i**2 - j**2):
                return 3
    # 남은 경우는 4
    return 4


n = int(input())
print(fourSquares(n))

 

문제 풀이

1. 자연수 n을 입력받는다.

2. dp[n]은 n을 표현하기 위한 최소 개수의 제곱수 합이다. 0과 1의 최소 개수의 제곱수 합은 0과 1이므로 dp 배열에 설정한다.

3. 이중 for문으로 i를 2부터 n+1까지의 범위를 설정하고(0과 1을 제외하고 n까지의 숫자를 모두 봐야 하기 때문에 +1), j를 1부터 i의 제곱근+1으로 설정한다.(1부터 i까지의 제곱근을 모두 봐야 하기 때문에 +1)

4. 최소 개수의 제곱수 합을 구하기 위해서 min함수를 사용한다. minValue값과 현재 dp배열 안에 값을 비교해서, 최소 개수의 제곱수 합을 구해 minValue에 넣어준다.

5. for문을 통해 구한 minValue을 해당 값의 인덱스에 넣어주고, 모든 반복문이 끝나면 마지막으로 구해진 n값을 출력하면 된다.

저작자표시 (새창열림)

'Koala - 7기 > 코딩테스트 준비 스터디' 카테고리의 다른 글

[백준/Python] 11726번 2xn 타일링  (0) 2022.07.17
[백준 / c++] 1895번 필터  (0) 2022.07.17
[백준 / Python] 1463번 1로 만들기  (0) 2022.07.16
[BOJ / Python] 1149 - RGB거리  (0) 2022.07.15
[백준/C++] 7579번 앱  (0) 2022.07.14
  1.  
  2. 문제 분석
  3.  
  4. 코드
  5. 문제 풀이
'Koala - 7기/코딩테스트 준비 스터디' 카테고리의 다른 글
  • [백준/Python] 11726번 2xn 타일링
  • [백준 / c++] 1895번 필터
  • [백준 / Python] 1463번 1로 만들기
  • [BOJ / Python] 1149 - RGB거리
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
Koala항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1883)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (38)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (31)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • C++
  • dfs
  • dp
  • BOJ
  • 파이썬
  • 백트래킹
  • 백준
  • BFS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[백준/Python] 17626번 Four Squares
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.