백준 1699번 제곱수의 합 풀이/코드 (파이썬) ('**2' 와 '*'의 차이..!)

코드만 궁금하신 분은

GitHub - Rhyankwon/algorithms

 

문제는 간단하다. 어떤 숫자가 입력되면 그 수를 (임의의 수의 제곱)의 합들로 나타내고, 그 때 사용되어지는 항의 최소 갯수를 출력하면 된다. 문제의 예시를 보면, 가령 11은 3^2 + 1^2 + 1^2 로 표현되어질 수 있지만 1^2 + 1^2 ... (11회반복) 으로 표현되어질 수도 있다. . 그러면 첫번째의 경우는 3개 항으로, 두번째의 경우는 11개의 항으로 이루어져 있기 때문에 답은 최소 항인 3이 된다.

 

당연한 말이지만 이보다 큰 수들은 엄청나게 많은 제곱수들의 조합으로 나타낼 수 있다. 나는 처음에 잘못 생각했던게, 그냥 큰 제곱수들로 계속해서 빼나가면 된다고 생각했다. 그런데 사실 엄청 큰 수 하나 + 자잘자잘한거 여러개 / 큰 수 여러개 이런식의 조합으로 나뉜다면 후자가 더 총 항의 갯수가 작은 경우가 생기기 때문에 내가 처음 말한식으로 풀면 풀이가 안돼버린다.

 

그렇게 해서..생각을 해보니까 그러면 dp를 해서 모든 경우의 수를 해보는 수밖에 없는 것 같더라 ..... ㅋㅋㅋㅋ 그래서 남의 풀이를 보고 .. 풀 수 밖에 없었다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 아니 뭐 혼자 해볼 수도 있겠지만 점호시간이 다가왔다고

 

내가 푼 방식은 이렇다.

 

1. 1부터 n(입력값)까지 반복한다.

2. 현재 값이 i이면, 1부터 i-1까지 반복하면서 현재 값의 제곱수의 합(최소 항의 수)를 확인한다.

 

이게 끝인데, 조금 더 자세히 말하자면 만약 지금 값이 43이면, dp[43] = dp[43 - 1^2] + 1 로 표현할 수도 있고, dp[43 - 2 ^2] +1 로 표현할 수도 있다. 1을 더하는 이유는 2^2라는 값이 항이 한개이니까. 그러면 dp[43-4] = dp[39]에 1을 더한 값을 구하고.. dp[43 - 6^2] + 1 = dp[7]+1 까지 값들을 확인하고 그중에 가장 작은 값이 dp[43]에 저장되는 식으로 식을 잘 활용하면 된다. 나는 무턱대고 min을 사용하려고 했는데 잘 안되서 남의 풀이를(...ㅋㅋㅋㅋ)보고 재수정했다.

 

요즘 특히 이런식으로 내가 못 푸는 문제가 많이 나와서, 다른 사람의 코드를 보면서 내가 얼마나 모자란지 알게 된다. 열심히 해야징..

 

--------------------------------------------------

 

이건 여담인데, 처음에 내 풀이가 안되서 왜이러지? 싶어서 다른 사람 풀이를 거의 그대로 갖다베꼇는데도 안되서 이건..뭔가 잘못됫다 싶었다. 그런데 보니까 그 사람의 풀이에서 내가 유일하게 베끼지 않은 하나는, 그 사람은 두번째 for문에서 j*j를 사용했고 나는 j**2를 사용했다는 점이다. 그런데 내 풀이는 안되더라고!!! 그래서 뭐지?에런가 하고 그 사람 풀이를 넣어서 돌려보니까 또 된다;;

그래서 나중에 위와 같은 코드를 만들어서 확인해봤는데 j*j로 제곱을 표현하는게 j**2보다 두배가량 빠르다; 몰랐음. 앞으로는 제곱 할 일이 있으면 **2보다는 그냥 곱을 활용하게 될 것 같다.