백준/ class3 문제 , 백준 파이썬 17626 , Four Squares

백준/ class3 문제 , 백준 파이썬 17626 , Four Squares

 

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

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

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

되게 어렵게 다가온 문제이다. 예시를 다 통과해도 계속틀리고 시간초과가 발생.
솔루션을 봐도 한번에 이해가 되지 않았었다. 오히려 잘못된 솔루션을 봐버려서 그 풀이법을 이해하려는데 시간을 써버렸다.

 

 

<문제 출처>

 

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

17626번: Four Squares

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

 

 

이게 자신의 수보다 작은 제곱수들 중에 제일 큰 제곱수가가 무조건 쓰이는게 아니라서 까다로웠다

 

 

예를 들면 23은 4의 제곱수가 쓰일 것 같지만 실제로 계산해보면

 

4*4 + 2*2 + 1*1 + 1*1 + 1*1 = 23   

 

이렇게 5개의 제곱수가 쓰인다. 4를 넘는 제곱수의 갯수는 안나온다고 하기 때문에

 

3*3 + 3*3 + 2*2 + 1*1 = 23

 

이렇게 4개가 쓰이는 계산이 맞다.

 

 

 

 

내가 본 솔루션 중에 잘못된것은

 

dp[n-(j**2)] +1   이 식을 그냥 적용 해버리던 것이였다.

 

자신의 수보다 작은 제곱수들중 가장 큰 값을 구하고

 

자신에서 그 제곱을 뺀 뒤

 

나온결과의 인덱스가 가지고 있는 경우의 수에다가 1을 더하는 것이다.

 

 

이 방식은 최소한의 갯수를 적용하지 않는다면 맞는 식이지만, 4개이하의 경우의 수를 가져와야하므로

 

여러 제곱수들을 다 확인해 나올 수 있는 경우의 수들을 다 확인해줘야 한다.

 

 

 

 

결국, 이 제곱수들을 다 확인해보려하니 for 문을 1부터 돌렸고 수가 커지면 다소 시간이 걸린다.

 

그래서 pypy3 로 통과하였다.

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

정답