모든 자연수는 최대 4개의 제곱수의 합으로 이루어져 있습니다. 예를 들면, 7 = 4 + 1 + 1 + 1과 같은 셈이죠. 다만, 항상 4개는 아닌데요. 예를 들면, 12 = 9 + 1 + 1 + 1이면서, 12 = 4 + 4 + 4인 것이죠. 그렇다면 어떤 자연수를 입력으로 받았을 때, 그 자연수의 최소 갯수의 제곱수의 양의 제곱근의 리스트를 반환하는 프로그램을 작성해봅시다. 예시:
입력 : 5
출력 : 2, 1
입력 : 7
출력 : 2, 1, 1, 1
입력 : 12
출력 : 2, 2, 2
입력 : 1572
출력 : 38, 8, 8
40개의 풀이가 있습니다.
import math, random
def sqrts(num):
a = [0, 0, 0, 0]
while a[0] ** 2 + a[1] ** 2 + a[2] ** 2 + a[3] ** 2 != num:
a[0] = int(random.randint(0, int(math.sqrt(num))))
a[1] = int(random.randint(0, int(math.sqrt(num))))
a[2] = int(random.randint(0, int(math.sqrt(num))))
a[3] = int(random.randint(0, int(math.sqrt(num))))
return a
randint를 이용해서 만들어봤습니다.
제가 쓴 풀이입니다(python 3.5.2). 욕심쟁이 알고리즘과 백트래킹을 사용하였습니다. func1()은 시험삼아 만든 것으로, 프로그램 내에서 직접적으로 사용되지는 않습니다.
def func1(n):
"""
욕심쟁이 알고리즘 사용
항상 4개 이하의 수를 반환하지는 않음
"""
import math
result = list()
while n != 0:
temp = int(math.sqrt(n) // 1)
result.append(temp)
n -= temp ** 2
del math
return result
def func2(n, a=4):
"""
욕심쟁이 알고리즘 + 백트래킹 사용
최대갯수를 a개로 제한
항상 최소갯수를 보장하지는 않음
"""
import math
result = list()
tempchangeflag = False #temp 변수가 40행에서 바뀌었을 때, 32행에서 값을 덮어쓰지 않도록 하기 위한 플래그
while n != 0:
if not tempchangeflag:
temp = int(math.sqrt(n) // 1)
tempchangeflag = False
result.append(temp)
n -= temp ** 2
if len(result) == a and n != 0:
while True:
if len(result) == 0: return None
temp = result.pop()
n += temp ** 2
temp -= 1
tempchangeflag = True
if temp != 0: break
del math
return result
def func3(n):
"""
func2() 함수를 활용, 최소 갯수를 찾음
"""
result = list()
for i in range(4, 0, -1):
temp = func2(n, i)
if temp == None: return result
result = temp
n = int(input('자연수 입력:'))
result = str(func3(n))
print(result[1:-1])
파이썬 3.x입니다
능력이 없어서 4개의 정수에서 0도 출력되고, 방법이 여러가지일 경우에 모두 출력합니다
num1 = int(input('입력 : '))
for i in range(num1+1):
if i**2 >= num1:
num2 = i-1
break
for a in range(0, num2+1):
for b in range(a, num2+1):
for c in range(b, num2+1):
for d in range(c, num2+1):
if a**2 + b**2 + c**2 + d**2 == num1:
print('출력 : {0}, {1}, {2}, {3}'.format(a,b,c,d))
break
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <math.h>
using namespace std;
int fun(const int n, int val, int depth, vector<int>& v);
int main()
{
int i, n, j;
vector<int> vec;
cin>>n;
for(i=1; i<=4; i++)
{
if(fun(n, 0, i, vec) != false)
{
while (!vec.empty()) {cout<<vec.back()<<endl; vec.pop_back();}
break;
}
}
return 0;
}
int fun(const int n, int s, int depth, vector<int>& v)
{
int i,ret=0,val=0;
if(depth == 0) return false;
while(++val*val <= n)
{
v.push_back(val);
if(s+val*val == n)
return true;
if(depth > 1)
if(fun(n, s+val*val, depth-1, v)) return true;
v.pop_back();
}
return false;
}
Python 3.4.2
from math import sqrt, modf, ceil
def find_a_b(n): # find a, b: if n = a**2 + b**2, else False
f, i = modf(sqrt(n/2))
if f == 0:
return i, i
else:
for x in range(1, ceil(sqrt(n/2))):
ff, ii = modf(sqrt(n - x**2))
if ff == 0:
return ii, x
return False
def find_a_b_c(n): # find a, b: if n = a**2 + b**2 + c**2, else False
f, i = modf(sqrt(n/3))
if f == 0:
return i, i, i
else:
for x in range(1, ceil(sqrt(n/3))):
m = n - x**2
if find_a_b(m) != False:
return find_a_b(m) + (x,)
return False
def find_a_b_c_d(n): # find a, b: if n = a**2 + b**2 + c**2 + d**2
f, i = modf(sqrt(n/4))
if f == 0:
return i, i, i, i
else:
for x in range(1, ceil(sqrt(n/4))):
k = n - x**2
if find_a_b_c(k) != False:
return find_a_b_c(k) + (x,)
gvn_num = int(input("Enter positive integer: "))
f1, i1 = modf(sqrt(gvn_num)) # 하나일때
if f1 == 0:
print("%d" % i1)
elif find_a_b(gvn_num) != False: # 두개의 제곱수의 합일때
print("%d, %d" % find_a_b(gvn_num))
elif find_a_b_c(gvn_num) != False: # 세개의 제곱수의 합일때
print("%d, %d, %d" % find_a_b_c(gvn_num))
else: # 네개의 제곱수의 합일때
print("%d, %d, %d, %d" % find_a_b_c_d(gvn_num))
제 알고리즘 상으로는 1572 의 경우 28, 28, 2 로 나타내는 것이 38, 8, 8 로 분해하는 것보다 계산이 더 빠릅니다.
pi@raspberrypi:~/example $ python3 find_sqr_sum.py
Enter positive integer: 1572
28, 28, 2
pi@raspberrypi:~/example $ python3 find_sqr_sum.py
Enter positive integer: 1571
39, 7, 1
pi@raspberrypi:~/example $ python3 find_sqr_sum.py
Enter positive integer: 16789
129, 12, 2
pi@raspberrypi:~/example $ python3 find_sqr_sum.py
Enter positive integer: 46781
216, 11, 2
pi@raspberrypi:~/example $ python3 find_sqr_sum.py
Enter positive integer: 1234567890
33984, 8925, 3
먼저 어떤 임의의 수를 입력받으면, 각 수의 제곱근들을 계산한 리스트에서 그 수보다 크기가 작은 제곱근들을 출력해, 만약 하나의 제곱근을 출력하면 그 수에서 제곱근을 뺀 수보다 작은 제곱근들을 출력해 지정합니다. 이렇게 이 과정을 반복하면 해결할 수 있습니다.
def ans(n):
if n == 0: return []
if int(n**0.5) == n**0.5: return [n]
temp = [i**2 for i in range(1,int(n**0.5)+1)]
temp2 = [n-i for i in temp if i <= n/2]
for i in temp2:
if i in temp: return [i]+ans(n-i)
temp3 = [i-j for i in temp2 for j in temp if j <= i/2 and i-j >=0]
for i in temp3:
if i in temp: return [i]+ans(n-i)
for i in temp3:
return ans(i)+ans(n-i)
n = int(input('자연수 입력: '))
print([int(i**0.5) for i in ans(n)])
package coading01;
import java.util.*;
public class Test01 {
public static void main(String[] args) {
/*
이제 막 자바 처음 배우는 학생이라 기본적인 문법밖에 모르겠네요ㅠㅠ제대로 되는건지..열심히 했습니다..
*/
Scanner robot = new Scanner(System.in);
int num;
System.out.print("입력 : ");
num = robot.nextInt();
/*
* 모든자연수는 최대 4개의 제곱수의 합이다. 자연수를 이루는 제곱수들이 최소의 갯수일때 제곱근들을 출력하라
*/
int tmp = 1;
while (true) {
if (tmp * tmp > num) {
tmp--;
break;
}
if (tmp * tmp == num) {
break;
}
tmp++;
}
// tmp에는 tmp를 제곱했을때 num을 초과하지 않는 최대 값이 저장 ;
int count = 0;
for (int tmp_i = tmp; tmp_i >= 1; tmp_i--) {
int i = tmp_i * tmp_i;
if (i == num) {
System.out.println("출력 : " + tmp_i);
count++; // 1
break;
}
}
if (count == 0) {
for (int tmp_i = tmp; tmp_i >= 1; tmp_i--) {
for (int tmp_j = tmp; tmp_j >= 1 ; tmp_j-- ) {
int i = tmp_i * tmp_i;
int j = tmp_j * tmp_j;
if (i + j == num){
System.out.println("출력 : " + tmp_i + "," + tmp_j);
count++;
break;
}
}
if (count == 1)
break;
}
}
//System.out.println(count);
if (count == 0) {
for (int tmp_i = tmp; tmp_i >= 1; tmp_i--) {
for (int tmp_j = tmp; tmp_j >= 1; tmp_j--) {
for (int tmp_k = tmp; tmp_k >= 1; tmp_k--) {
int i = tmp_i * tmp_i;
int j = tmp_j * tmp_j;
int k = tmp_k * tmp_k;
if (i + j + k == num) {
System.out.println("출력 : " + tmp_i + "," + tmp_j + "," + tmp_k);
count++;
break;
}
}
if (count == 1)
break;
}
if (count == 1)
break;
}
}
if (count == 0) {
for (int tmp_i = tmp; tmp_i >= 1; tmp_i--) {
for (int tmp_j = tmp; tmp_j >= 1; tmp_j--) {
for (int tmp_k = tmp; tmp_k >= 1; tmp_k--) {
for (int tmp_h = tmp; tmp_h >= 1; tmp_h--) {
int i = tmp_i * tmp_i;
int j = tmp_j * tmp_j;
int k = tmp_k * tmp_k;
int h = tmp_h * tmp_h;
if (i + j + k + h == num) {
System.out.println("출력 : " + tmp_i + "," + tmp_j + "," + tmp_k + "," + tmp_h);
count++;
break;
}
}
if (count == 1)
break;
}
if (count == 1)
break;
}
if (count == 1)
break;
}
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int num1(int i){
int j,k,l,n;
int m;
m=sqrt(i);
if(i==m*m){
printf("%d\n",i);
return 0;
}
for(j=m;j>=1;j--){
for(k=i-j;k>=1;k--){
if(j*j+k*k==i){
printf("%d %d\n",j,k);
return 0;
}
}
}
for(j=m;j>=1;j--){
for(k=i-j;k>=1;k--){
for(l=i-j-k;l>=1;l--){
if(j*j+k*k+l*l==i){
printf("%d %d %d\n",j,k,l);
return 0;
}
}
}
}
for(j=m;j>=1;j--){
for(k=i-j;k>=1;k--){
for(l=i-j-k;l>=1;l--){
for(n=i-j-k-l;n>=1;n--){
if(j*j+k*k+l*l+n*n==i){
printf("%d %d %d %d\n",j,k,l,n);
return 0;
}
}
}
}
}
return 0;
}
int main(int argc, char *argv[])
{
int i;
scanf("%d",&i);
num1(i);
scanf("%d",&i);
system("PAUSE");
return 0;
}
7223의 경우는 7개가 나오네요. 1,000,000 까지 해봤을 때는 최대 7개였습니다. 신기하네요... 혹시 8,9,10 개도 나올 수 있는 걸까요?
clear all
close all
clc
%% input value
input_n=input('입력 : ');
%% processing
element_cnt=0; % number of the square-values. according to the problem, this can be equal to or less than 4
element_set=[]; % answer storage
remain_val=input_n; % for example, 13 - 9 = 4...
% checking time
t_start=clock;
while remain_val > 0
% obtain the square number
sqrt_num=floor(sqrt(remain_val));
% insert the square number into the answer storage
element_cnt=element_cnt+1;
element_set(element_cnt)=sqrt_num;
% update the remaining number
remain_val=remain_val-sqrt_num^2;
end
t_finish=clock;
%% display output
display_string='출력 : ';
confirm_string=['확인 : ' num2str(input_n) ' = '];
for k=1:element_cnt
if k < element_cnt
display_string=[display_string ' ' num2str(element_set(k) ) ' ,' ];
confirm_string=[confirm_string ' ' num2str(element_set(k)^2) ' +' ];
else
display_string=[display_string ' ' num2str(element_set(k) )];
confirm_string=[confirm_string ' ' num2str(element_set(k)^2)];
end
end
elapsed_time=etime(t_finish,t_start);
disp(display_string);
disp(confirm_string);
disp(' ');
if elapsed_time < 60
disp(['걸린 시간 : ' num2str(elapsed_time ) ' 초']);
elseif elapsed_time < 3600
disp(['걸린 시간 : ' num2str(elapsed_time/60 ) ' 분']);
else
disp(['걸린 시간 : ' num2str(elapsed_time/3600) ' 시']);
end
% return
%% check if there is a case with element_cnt > 4, which is a counter-example of the problem definition
disp(' ');disp(' ');disp(' ');disp(' ');disp(' ');
test_n_set=(1:1:1e6);
test_n_len=length(test_n_set);
result_cnt_time=zeros(test_n_len,2);
for test_n_idx=1:test_n_len
test_n=test_n_set(test_n_idx);
if round(log10(test_n)-log10(2))==log10(test_n)-log10(2)
disp([' current test... ' num2str(test_n) ' ' datestr(now,16)]);
end
remain_val=test_n;
test_cnt=0;
test_set=[];
t1=clock;
while remain_val > 0
sqrt_num=floor(sqrt(remain_val));
test_cnt=test_cnt+1;
test_set(test_cnt)=sqrt_num;
remain_val=remain_val-sqrt_num^2;
end
t2=clock;
result_cnt_time(test_n_idx,:)=[test_cnt etime(t2,t1)];
end
figure;
bar(test_n_set,result_cnt_time(:,1));
disp([' ' num2str(test_n_set(end)) '까지 검사했을 때 최대 갯수 : ' num2str(max(result_cnt_time(:,1)))]);
결과 먼저...
given_number = 7223 : result = 7223
Num[0] = 1
Num[1] = 2
Num[2] = 57
Num[3] = 63
#include <stdio.h>
uint8_t status;
uint16_t n[4];
uint16_t given_number;
uint16_t result;
uint8_t check_num(uint16_t num)
{
uint16_t i;
uint16_t maxnum;
//제곱하여 원 숫자를 넘어가는 최대수를 찾음
// n = a^2 + b^2 + c^2 + d^4 일 때 b,c,d = 0 이고 a^2 가 원 숫자보다 크면 count 멈춤
for(i = 1; i < num; i++)
{
result = i * i;
if ( result > num)
{
maxnum = i;
break;
}
}
//이 이후는 단순하게 곱하여 찾는 수임.
for(n[0] = 0; n[0] < maxnum; n[0]++)
{
for(n[1] = 0; n[1] < maxnum;n[1]++)
{
for(n[2] = 0; n[2] < maxnum; n[2]++)
{
for(n[3] = 0; n[3] < maxnum; n[3]++)
{
result = (n[0]*n[0]) + (n[1]*n[1]) + (n[2]*n[2]) + (n[3]*n[3]);
if(result == num) return 1;
}
}
}
}
return (0);
}
int main(void)
{
given_number = 7223;
status = check_num(given_number);
if(status)
{
printf(" given_number = %d : result = %d \n", given_number, result);
printf(" Num[0] = %d\n",n[0]);
printf(" Num[1] = %d\n",n[1]);
printf(" Num[2] = %d\n",n[2]);
printf(" Num[3] = %d\n",n[3]);
}
return (0);
}
def split(a):
b=int(a)
result=[]
for i in range(a,0,-1):
while i**2<=b:
result.append(i)
b-=i**2
if b==0:
print(a,'는',result,'의 제곱수로 이루어져 있습니다.')
return
public class MyTest2 {
public static void main(String[] args) {
int num = 12; //분리하고자 하는 수
int result = 0;
loop:
for (int i1 = 0; (i1*i1) <= num; i1++){
for (int i2 = i1; (i1*i1)+(i2*i2) <= num; i2++){
for (int i3 = i2; (i1*i1)+(i2*i2)+(i3*i3) <= num; i3++){
for (int i4 = i3; (i1*i1)+(i2*i2)+(i3*i3)+(i4*i4) <= num; i4++){
result = (i1*i1) + (i2*i2) + (i3*i3) + (i4*i4);
if (result == num) {
System.out.println(result + ": " +i4+" "+i3+" "+i2+" "+i1);
//자연수의 최소 갯수의 제곱수의 양의 제곱근의 리스트를 반환하는 프로그램이니,
//제일 처음 한 건 구하고 바로 빠져나오기
break loop;
}
}
}
}
}
}
}
def find_squares(n):
loop = 0
min_arr = None
# n 부터 1까지 첫번째 제곱수를 대입
for a in range(n, 1, -1):
if a ** 2 < n:
y = n - a ** 2
y_arr = [a]
b = int(math.sqrt(y))
# 첫번째 제곱수가 선택되었을때 다음 제곱수를 찾음
while True:
loop+=1
# 제곱값이 y보다 작을경우 요소로 추가
if b ** 2 <= y:
y_arr.append(b)
y -= b**2
b = int(math.sqrt(y))
# 이미 제곱수의 갯수가 현재 계산된 최소보다 크면 불필요하게 계산X
if min_arr is not None and len(y_arr) >= len(min_arr):
break
if y == 0:
if min_arr is None or len(min_arr) > len(y_arr):
min_arr = y_arr
break
print('loop_cnt:', loop)
return min_arr
print(find_squares(5))
print(find_squares(7))
print(find_squares(12))
print(find_squares(1572))
OUTPUT
loop_cnt: 1
[2, 1]
loop_cnt: 3
[2, 1, 1, 1]
loop_cnt: 5
[2, 2, 2]
loop_cnt: 81
[34, 20, 4]
마지막 결과인 1572에 대한 값이 34, 20, 4라는점이 좀 다르긴합니다만 최소갯수 조건은 맞습니다.
N을 구성하는 제곱수의 목록중 가장 짧은 것을 구할 때
N - 1 (1^2)
N - 4 (2^2)
N - 9 (3^2) ...
이런식으로 0까지 내려가면서 제곱수의 목록이 가장짧은 것을 골라서, 빼준 제곱수를 추가해주면 됩니다.
전형적인 DP문제네요.
def solve(n):
if n < 1:
return []
u = [[], [1]]
for i in range(2, n+1):
j = 1
lowCount = n
u.append([])
while True:
k = i - j*j
if k < 0:
break
if len(u[k]) + 1 < lowCount:
lowCount = len(u[k]) + 1
u[-1] = u[k] + [j]
j += 1
return u[-1]
n = int(input())
print(', '.join(str(x) for x in solve(n)))
import java.util.Scanner;
class Square{
int num ;
int bigSquare(){
int result=0;
for(int i=num; i>0; i--){
if(num>i*i){
result = i*i;
break;}
}
return result;
}
}
class end{
public static void main(String arg[]){
Scanner input = new Scanner(System.in);
String msg = "";
Square ob = new Square();
ob.num=1000;
while(ob.num>0){
ob.bigSquare();
System.out.print(ob.bigSquare() + " ");
ob.num= ob.num - ob.bigSquare() ;
}
}
}
import math
List1 = []
t = int(math.sqrt(N))
print("t=%s" %t)
sum1 = 0
while(sum1 < N):
for i in range(t+1)[::-1]:
i = i**2
if (sum1+i) <= N :
List1.append(i)
sum1 = sum(List1)
if sum1 == N :
break
while(List1.count(0)):
List1.remove(0)
print("List1 = %s" %str(List1))
using namespace std;
struct qInfo { int q; }; struct testCaseT { int pNum=0; int qNum=0; qInfo *pQuest = new qInfopNum; int chc=0; };
int inputPQuest(qInfo qI,int qNum,int question[]) { char str[256]; char context = NULL; int chk=0; int i = 0; int tokStr2[256]; scanf("%d ",&tokStr2[0]); for(i = 1; i <= tokStr2[0]; i++) { if(i == tokStr2[0]) scanf("%d",&tokStr2[i]); else scanf("%d ",&tokStr2[i]); } //char tok = strtok_s(str," ",&context); / while(tok != NULL) { tokStr2[i++] = tok; tok = strtok_s(NULL," ",&context); }/ qI->q = tokStr2[0]; if(tokStr2[0] == qNum || tokStr2[0] ==0) chk = -1; for(int i = 1; i < tokStr2[0] +1; i++) { question[tokStr2[i]-1]++; } return chk; } void inputTest(testCaseT T) { char str[256]; int tokStr[256]; int i = 0; int th = 0; char *context = NULL; scanf("%d %d",&tokStr[0],&tokStr[1]);
/*char *tok = strtok_s(str," ",&context);
while(tok != NULL)
{
tokStr[i++] = tok;
tok = strtok_s(NULL," ",&context);
}*/
T->pNum = tokStr[0];
T->qNum = tokStr[1];
int *question = new int[tokStr[1]]();
for(int i = 0; i <tokStr[0]; i++)
{
if(T->chc==0) T->chc= inputPQuest(&T->pQuest[i],tokStr[1],question);
else th=inputPQuest(&T->pQuest[i],tokStr[1],question);
}
for(int i = 0; i <tokStr[1]; i++)
{
if(question[i] == 0) T->chc = -1;
}
}
int main() { int num; cin >> num; testCaseT *T = new testCaseT[num]; cin.clear(); cin.ignore(256,'\n'); for(int i = 0; i < num; i++) { inputTest(&T[i]); } for(int i = 0; i < num; i++) { if(T[i].chc == -1)cout << "NO"<<endl; else cout << "YES"<<endl; } return 0; }
import Foundation
fileprivate func findBiggestRootLessThan(_ value: UInt) -> UInt {
let dbValue: Double = Double(value)
let biggestRoot = UInt(floor(sqrt(dbValue)))
return biggestRoot
}
fileprivate struct P1Result {
var numberCount: UInt
var sum: UInt
var numberString: String
}
fileprivate func printRootsConsistsNaturalNumber(theNum: UInt) {
var resultArray: Array = Array()
let biggest: UInt = findBiggestRootLessThan(theNum)
for i in 0..(repeating:0, count:4)
var roots = Array(repeating:0, count:4)
// print("to find: \(toFind), limit: \(limit)")
for j in 0..<4 {
if toFind > limit { toFind = limit }
let root = findBiggestRootLessThan(toFind)
guard root > 0 else {
break
}
roots[j] = root
squares[j] = root * root
if squares[j] > 0 {
sum += squares[j]
count += 1
if squares[0] < theNum/4 { break }
}
toFind = theNum - sum
if sum >= theNum { break }
}
if sum == theNum {
var numberString: String = ""
for k in 0..<4 {
if roots[k] > 0 {
if k > 0 { numberString += ", " }
numberString += String(roots[k])
}
}
let result = P1Result(numberCount: count, sum: sum, numberString: numberString)
resultArray.append(result)
}
}
var array = resultArray.sorted() { $0.numberCount < $1.numberCount }
print("Found : \(array[0].numberString)")
}
/**
* command line에서 0 입력하면 종료
* 다른 수를 입력하면 결과 출력
* O(log N) 수준
*/
func solveProblem1WithSortedArray() {
var theNum = UInt(0)
repeat {
guard let input = UInt(readLine() ?? "0") else {
print("Unavailable Input")
break
}
theNum = input
if theNum == 0 { break }
printRootsConsistsNaturalNumber(theNum: theNum)
} while theNum > 0
}
파이썬 3으로 작성했습니다. Class가 익숙하지 않아서 class로 만들어서 풀어보았습니다.
답: 1572: [39, 7, 1, 1]
코드:
import math
class sumOfFourSquare:
inputNum = 0
resultList = []
def __init__(self, inputNum):
self.inputNum = inputNum
def insertMaxNum(self, inputNum):
self.resultList.append(0 if inputNum == 0 else int(math.sqrt(inputNum)))
def testResult(self):
if(self.returnListResult() == self.inputNum):
return True
return False
def returnListResult(self):
finalResult = 0
for i in self.resultList:
finalResult += (i*i)
return finalResult
def changeLastInsertedNum(self):
lastNum = self.resultList.pop()
if lastNum == 0:
self.changeLastInsertedNum()
self.insertMaxNum(self.inputNum - self.returnListResult())
else:
self.resultList.append(lastNum - 1)
def findFourNumber(self):
for i in range(4):
self.insertMaxNum(self.inputNum - self.returnListResult())
while True:
if(self.testResult()):
print(str(self.inputNum) + ": " + str(self.resultList))
return
self.changeLastInsertedNum()
if __name__ == "__main__":
sumCal = sumOfFourSquare(1572)
sumCal.findFourNumber()
import math
def test(num,li,depth=0):
temp = int(math.sqrt(num))
while True:
if depth>3:
return li
remain = num - temp*temp
if remain < 0:
return li
else:
li.append(temp)
li=test(remain,li,depth+1)
if len(li) != 4:
temp = temp -1
li.pop()
else:
break
return li
def test2(num,a):
result = []
remain = num
temp = 0
temp_flag=False
while True:
if not temp_flag:
temp = int(math.sqrt(remain))
remain = remain - temp**2
result.append(temp)
if remain >0 and len(result)<a:
temp_flag=False
elif remain==0:
return result
else:
while True:
try:
temp=result.pop()
except:
return []
remain = remain + temp**2
temp = temp - 1
temp_flag=True
if temp >= 0 :
break
def main():
print test2(1572,3)
if __name__ == "__main__":
main()
파이썬 2.7 문법입니다.
하다보니 기존코드랑 비슷해지네요
첫번째 함수는 처음에 재귀함수밖에 생각이 안나 짜본 코드이고
두번째 함수는 반복문으로 짜본 코드입니다.
제곱근 리스트는 여러가지 경우가 있네요. 그 중 길이가 최대 4개인 경우를 골라내는 프로그램을 짰습니다. 1572는 예제에 있는 값 뿐만아니라 [39, 7, 1, 1] 도 답이 될 수 있네요.
import math
nInit = 1572
rootStart = int(math.sqrt(nInit))
rootList = []
while 1:
rootList = [rootStart]
n = nInit
n = n - rootStart ** 2
while n != 0:
root = int(math.sqrt(n))
rootList.append(root)
n = n - root**2
if len(rootList) <= 4:
break
else:
rootStart = rootStart -1
print(rootList)
자연수 N 이 K개 제곱수 (1 <= K <= 4)의 합이라면,
제곱수 모두가 N/K 미만일 경우 합이 N이 될 수 없습니다.
따라서 제곱수 중 N/K 이상인 제곱수가 적어도 하나는 반드시 존재합니다.
=> 합이 N이 되는 제곱수 중 가장 큰 수를 M이라 하면,
N/K <= M * M <= N,
sqrt(N/K) <= M <= sqrt(N)
입니다.
N이 작아질수록 탐색 시간이 짧아지므로, 크기가 큰 제곱수부터 시도하는 것만으로도 수행시간을 상당히 줄일 수 있습니다.
.
아래 sumsquare()는 "합이 N이 되는 K개 이하 제곱수들" 중 가장 큰 제곱수를 M이라 할 때,
가능한 모든 M에 대해 "합이 (N - M * M)이 되는 (K-1) 개 이하 제곱수들"을 찾아서
그 중 가장 짧은 답을 리턴합니다.
단순하게 풀면 쉽지만 재귀호출 연습한다 생각하면 꽤 재미난 문제네요.
from math import floor, ceil, sqrt
def sumsquare(N, K):
if N == 0:
return [] # 탐색 성공
elif N < 0 or K <= 0:
return [-1] * 5 # 탐색 실패. 리스트 길이로 판별하므로 의미없이 긴 리스트를 리턴
else:
minK = [-1] * 5
for M in range(ceil(sqrt(N / K)), ceil(sqrt(N)) + 1):
ret = sumsquare(N - M**2, K - 1) # <-- 여기가 핵심
if len(ret) < len(minK):
minK = [M] + ret
return minK
inp = [5, 7, 12, 1572]
for N in inp:
print(N, sumsquare(N, 4))
package jjy;
import java.util.Scanner;
public class test {
public static void main(String[] args) {
// TODO Auto-generated method stub
int i, a=0, b=0, c=0, d=0;
int num;
int tmp;
int sum=0;
Scanner test = new Scanner(System.in);
System.out.println("원하는 자연수는?");
num = test.nextInt();
for(i=0; i<Integer.MAX_VALUE; i++)
{
if((i*i<=num)&&((i+1)*(i+1)>num))
{
System.out.println(i);
break;
}
}
tmp=i;
boolean e=true;
for(a=0; a<tmp; a++){
for(b=0; b<tmp; b++){
for(c=0; c<tmp; c++){
for(d=0; d<tmp; d++){
if((a*a+b*b+c*c+d*d==num)&&(e)){
System.out.println(a+", "+b+", "+c+", "+d);
e=false;
break;
}
}
}
}
}
}
}
올리기 약간 민망한 코드지만 답은 나옵니다.
for문 중첩을 간단하게 처리할 방법이 없을까요..
#include<iostream>
using namespace std;
void main(void)
{
int num;
int arr[4];
int count;
int sum = 0;
cin >> num;
int start = sqrt(num);
//cout << start << " ";
if (start * start == num)
exit(1);
sum = start;
for (int i = 1; i <= start; i++)
{
for (int j = 1; j <= start; j++)
{
if (num == i*i + j*j)
{
cout << i << " " << j << endl;
exit(1);
}
}
}
for (int i = 1; i <= start; i++)
{
for (int j = 1; j <= start; j++)
{
for (int k = 1; k <= start; k++)
{
if (num == i*i + j*j + k*k)
{
cout << i << " " << j << " " << k << endl;
exit(1);
}
}
}
}
for (int i = 1; i <= start; i++)
{
for (int j = 1; j <= start; j++)
{
for (int k = 1; k <= start; k++)
{
for (int l = 1; l <= start; l++)
{
if (num == i*i + j*j + k*k + l*l)
{
cout << i << " " << j << " " << k << " " << l << endl;
exit(1);
}
}
}
}
}
}
파이썬 3.6
제곱수 조합의 갯수가 4개 이상인 것도 있는 것 같습니다. 조건을 4개 이하인 것으로 제한하여 조합을 찾도록 하였습니다.
import math
def powerroot(n):
sum,roots,roots_list,result = 0,[],[],[]
for h in [i for i in range(1,int(math.sqrt(n))+1)][::-1]:
sum += h*h
roots.append(h)
while True:
for i in [i for i in range(1,int(math.sqrt(n))+1)][::-1]:
if i*i < n and sum + (i*i) <= n:
sum += i*i
roots.append(i)
break
if sum >= n:
break
if len(roots) <= 4:
roots_list.append([len(roots),sorted(roots,reverse=True)])
sum,roots = 0,[]
# print(roots_list)
for i in roots_list:
if i[0] == min(roots_list)[0]:
if i not in result:
result.append(i)
print(i[0],i[1])
if __name__ == "__main__":
n = int(input())
powerroot(n)
*결과값
5
2 [2, 1]
7
4 [2, 1, 1, 1]
12
3 [2, 2, 2]
1572
3 [34, 20, 4]
3 [28, 28, 2]
3 [32, 22, 8]
3 [38, 8, 8]
2000
2 [44, 8]
2 [40, 20]
import math
def squaresum(a):
x = math.sqrt(a)
if x.is_integer():
return [[int(x)]]
result = list()
b = math.ceil(x/2)
c = math.floor(x)
for i in range(b, c+1):
for j in range(i+1):
if i*i + j*j == a:
result.append([i, j])
if result:
return result
for i in range(b, c + 1):
for j in range(i + 1):
for k in range(j+1):
if i*i + j*j + k*k == a:
result.append([i, j, k])
if result:
return result
for i in range(b, c + 1):
for j in range(i + 1):
for k in range(j + 1):
for l in range(k+1):
if i*i + j*j + k*k + l*l == a:
result.append([i, j , k, l])
return result
print(squaresum(int(input())))
def sqrnum(n):
dic = {1:[1,[1,1]]}
for i in range(1,n+1):
new=[i,[]]
for j in range(1,i+1):
if j*j==i:
dic[i]=[1,[j,i]]
break
elif j*j<i:
new = dic[i-j*j][0]+1<=new[0] and [dic[i-j*j][0]+1, dic[i-j*j][1][0:(dic[i-j*j][0])]+[j]+[i]] or new
dic[i]=new
return dic[n][1][0:dic[n][0]]
sqrnum(1572)
#include <stdio.h>
#include <stdlib.h>
struct Seq {
int length, arr[10000], val;
};
struct Seq sqrnum(int n) {
struct Seq neew;
struct Seq *a = malloc(sizeof(struct Seq)*n);
for (int i = 1; i < n + 1; i++) {
a[i - 1].length = i;
for (int j = 1; j < i+1; j++) {
if (j*j == i) {
neew.length = 1;
neew.arr[0] = j;
neew.val = i;
a[i - 1] = neew;
break;
}
else if (j*j < i) {
if (a[i - j * j - 1].length + 1 <= a[i-1].length) {
neew.length = a[i - j * j - 1].length + 1;
for (int k = 0; k < neew.length; k++) {
neew.arr[k] = a[i - j * j - 1].arr[k];
neew.val= i;
}
neew.arr[neew.length - 1] = j;
}
}
a[i - 1].length = neew.length;
for (int k = 0; k < a[i - 1].length; k++) {
a[i - 1].arr[k] = neew.arr[k];
a[i - 1].val = neew.val;
}
}
}
neew.length = a[n-1].length;
for (int k = 0; k < a[n - 1].length; k++) {
neew.arr[k] = a[n-1].arr[k];
neew.val = a[n-1].val;
}
free(a);
return neew;
}
int main() {
int n = 1572;
struct Seq b;
b=sqrnum(n);
for (int i = 0; i < b.length; i++) {
printf("%d, ", b.arr[i]);
}
printf("\n");
return 0;
}
package codingdojang;
import java.util.Scanner;
public class ex130 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a=0,b=0,c=0,d=0;
int min = 5;
int temp = 4;
int mina=0,minb=0,minc=0,mind=0;
for(a=0; a*a <=n; a++) {
for(b=0; a*a + b*b <=n; b++) {
for(c=0; a*a + b*b + c*c <=n; c++) {
for(d=0; a*a + b*b + c*c + d*d <=n; d++) {
temp = 4;
if(a==0) temp--;
if(b==0) temp--;
if(c==0) temp--;
if(d==0) temp--;
if(a*a + b*b + c*c + d*d == n) {
if(min > temp) {
min = temp;
mina = a;
minb = b;
minc = c;
mind = d;
}
}
}
}
}
}
System.out.println(min);
System.out.println("a = " + mina + ",b = " + minb + ",c = " + minc + ",d = " + mind);
}
}
import sys, math
# 제곱한 값이 n 이하의 square numbr list [1,4,9,16,...]
def get_square_list( n ):
l = []
t = 1
while (t ** 2) <= n:
l.append(t**2)
t += 1
#print(" -> {}".format(l))
return l
n = int(sys.argv[1])
def func(n):
if n == 0: return []
min_l = []
min_len = n
for x in list(reversed(get_square_list(n))):
quo = int(n / x)
remain = n % x
l = [x] * quo + func(remain)
if len(l) <= min_len:
min_l = l
min_len = len(l)
return min_l
l = func(n)
l = list(map(lambda x: int(math.sqrt(x)), l))
print("{}".format(l))
import java.util.Scanner;
import java.util.ArrayList;
public class KimSanghyeop {
public static void main(String args[])
{
Scanner sc =new Scanner(System.in);
System.out.print("입력 : ");
int input = sc.nextInt();
int f1,f2,f3,f4;
String res="";
int cnt=4;
for(f1=0;f1*f1<=input;f1++)
{
for(f2=0;f2<=f1;f2++)
{
for(f3=0;f3<=f2;f3++)
{
for(f4=0;f4<=f3;f4++)
{
if(f1*f1 + f2*f2 + f3*f3 + f4*f4 == input)
{
//System.out.println(cnt);
if(f2==0 && cnt>=1)
{
cnt=1;
res = f1 +"" ;
}
else if(f3==0 && cnt>=2)
{
cnt=2;
res = f1+","+f2 ;
}
else if(f4==0 && cnt >=3)
{
cnt=3;
res = f1+","+f2 +","+ f3;
}
else if(cnt >=4)
{
cnt=4;
res = f1+","+f2 +","+ f3+","+f4;
}
}
}
}
}
}
System.out.println("결과 : "+res);
}
}
n=int(input("자연수 n을 입력하십시오: "))
elst=[]
for n1 in range(0,2): #모든 쌍을 찾는 것이 아니라 최소 개수를 찾는 것이므로 앞이 무조건 0이나 1이라 가정.
for n2 in range(0,int(n**(1/2))+1):
for n3 in range(0,int(n**(1/2))+1):
for n4 in range(0,int(n**(1/2))+1):
if n1**2+n2**2+n3**2+n4**2==n and sorted([n1,n2,n3,n4]) not in elst: #4개의 숫자를 각 각 제곱한 결과가 n이면서 이들을 정렬한 리스트가 elst에 들어있지 않으면 elst에 추가함.(중복을 막기 위함)
elst.append([n1,n2,n3,n4])
for lst in elst: #elst안의 리스트 중 0을 요소로 가진 리스트에서 0을 제거
while 0 in lst:
lst.remove(0)
for lst in elst:
if len(lst)==len(elst[0]): #elst의 맨 앞의 리스트(elst[0])가 가장 작은 길이를 가지므로 어떤 리스트의 길이가 그 길이와 같다면 최소 개수의 제곱수의 양의 제곱근 리스트임.
print(len(lst),lst)
결과
자연수 n을 입력하십시오: 1572
3 [2, 28, 28]
3 [4, 20, 34]
3 [8, 8, 38]
3 [8, 22, 32]
제곱수로 입력 받은 수를 조합하는 경우를 구해보았습니다. 직접 개수를 세는 단순한 알고리즘이라 입력 받은 숫자가 커질수록 모든 조합을 찾는 데 시간이 너무 길어지네요,,
import math
import time
start = time.time()
inum = input('Enter the number:')
final_list=list()
sub_list = list()
a_max_num = int(math.sqrt(inum)) #176의 경우 13까지
a_min_num = int(math.sqrt(inum/4)) #176의 경우 6까지
for a in range(a_max_num, a_min_num, -1): #math.sqrt(inum/4) == a일 때, 네제곱수가 최소 개수 조합일 수는 없다.
sub_list.append(a)
isum = inum - a**2
b_max_num = min(int(math.sqrt(isum)),a) #일반성을 잃지 않는 한에서 카운팅 수 최소화
for b in range(b_max_num+1)[::-1]:
sub_list.append(b)
isum = inum - a**2 - b**2 #isum하고 inum하고 구분
c_max_num = min(int(math.sqrt(isum)),b)
for c in range(c_max_num+1)[::-1]:
sub_list.append(c)
isum = inum - a**2 - b**2 - c**2
d_max_num = min(int(math.sqrt(isum)),c)
for d in range(d_max_num+1)[::-1]:
sub_list.append(d)
d_temp = tuple(sub_list)
if sum(list(map(lambda x: x**2,d_temp))) == inum : final_list.append(d_temp) #합이 inum이면 append
sub_list.remove(d)
#print(final_list)
sub_list.remove(c)
sub_list.remove(b)
sub_list.remove(a)
max_count_temp = -1
for series in final_list:
count_temp = series.count(0)
if max_count_temp < count_temp:
max_count_temp = count_temp
for series in final_list:
if series.count(0) == max_count_temp:
print('드디어,', series)
print(time.time()-start)
초보의 불완전한 방식입니다. - 나머지를 최소화 해가므로 갯수는 적은거 같은데...
n = int(input("어떤 자연수는 = "))
sq = [x**2 for x in range(n+1) if x**2 <n ]
s = []
for i in range(len(sq)):
dd = sq[-(i+1)]
if dd != 0 and n//dd > 0 :
s.append(dd**(1/2))
n = n%dd
elif dd ==0 :
s.append(dd)
print(s)
초보의 불완전한 방식 - 속도면에서... 근데 숫자가 커지니 갯수가 많아지네요...
n = int(input("어떤 자연수는 = "))
s = []
while n != 0:
sq = int(n**(1/2))
s.append(sq)
n = n%(sq**2)
print(s)
// Rust
// sum = a^2+b^2+c^2+d^2 계산을 위해 a>=b>=c>=d 제한을 두고,
// a에 sum-1부터 1까지 주면서, 추가 n개(0,1,2,3) 항의 합으로 sum-a^2을 만드는 함수를 재귀로 돌렸습니다.
// 재귀함수의 마지막 판별에서 n==0일때 sum==0이면 통과(Option::Some 반환), 아니면 None 반환입니다.
// sum=1572인 경우 [28, 28, 2], [32, 22, 8], [34, 20, 4] 도 있습니다.
fn sum_square(sum: usize) {
for i in (1..sum).rev() {
if i * i > sum { continue; }
for n in 0..4 {
if let Some(v) = f(n, &[i], sum-i*i) {
println!("");
println!("{} =>{}항 {:?}", sum, n+1, v);
}
}
}
}
fn f(n:usize, arr: &[usize], sum: usize) -> Option
if n == 0 {
if sum == 0 { return Some(arr.to_vec());}
else { return None; }
}
let l = arr.len();
let last = arr[l-1];
let mut result = vec![];
for i in (1..=last).rev() {
if i * i > sum { continue;}
let mut vec = arr.to_vec();
vec.push(i);
if let Some(v) = f(n-1, &vec[..], sum-i*i) {
result = v;
}
}
if result.is_empty() { None }
else { Some(result) }
}
for문 이용해서 가장 짧은 제곱수를 찾는 방식으로 만들었습니다. 해보니 겁내 빠르네요.
15212413272 정도 되는 숫자도 1초면 찾습니다.
def findsq(x):
a= x**0.5
if int(a) == a:
return print("제곱수는", int(a))
for i in range(0, int(a)):
for j in range(0, int(a)):
a2= (x-(i**2)-(j**2))**0.5
for k in range(int(a2), 0, -1):
a3 = (x-(i**2)-(j**2)-(k**2)) **0.5
if int(a3) == a3:
return print("제곱수는", i,j,k,int(a3))
findsq(1572)
def sqrNum(num, lst):
global minSu
if len(lst) >= minSu:
return
if num < 4:
if len(lst) + num < minSu:
for _ in range(num):
lst.append(1)
res.clear()
res.append(lst)
minSu = len(lst)
return
sq = int(num**0.5)
for i in range(sq,1,-1):
newlst = lst.copy()
newlst.append(i)
sqrNum(num - i*i, newlst)
for n in [5, 7, 12, 1572]:
minSu = n
res = []
sqrNum(n, [])
print(" 입력: {0}, 출력: {1}".format(n,res[0]))