BOJ_17626 : Four Squares

 

👉 문제링크

17626번: Four Squares

---

---

🔸 문제 분석 🔸

• 입력받은 n을 제곱수의 합으로 표현할 때 최소한의 경우의 수를 출력한다.
• dp 와 브루트 포스 풀이 두 가지가 가능하다.
  • dp
    • dp[n] 리스트는 n을 만드는데 들어가는 '제곱수 합 경우의 수의 최소값'을 저장한다.
    • dp[0] = 0, dp[1] = 1 로 초기화한다.
    • dp[n]을 구할 때, 1부터 j의 제곱수(j**2)가 i보다 커질때까지 반복하며 최소값을 찾는다.
      • min_v : i에서 j**2를 뺀 dp값( dp[i-j**2] )의 최소값
      • dp[i]에 방금 구한 최소값(min_v) + 뺐던 j**2(경우의 수 1)를 저장한다. (dp[i] = min_v + 1)
      • ex) dp[5]를 만들때, dp[4]의 값 (1) + j**2의 경우의 수(1) 해서 2를 저장
        => 5를 만드는데 숫자 2개만 있으면 된다. (4 + 1)
  • 브루트 포스
    • 문제 조건에 제곱수의 합을 4이하의 수로 나타내라 했으므로, 답은 1,2,3,4 중 하나이다.
      • n의 제곱근이 정수이면(n이 제곱수) : 1
      • n - i**2의 제곱근이 정수이면 : 2                    => (n-i**2) + (i**2) 로 표현 가능 (26은 25+1 로 표현)
      • n - i**2 - j**2 의 제곱근이 정수이면 : 3
      • 이 외엔 모두 4

🔸 dp 풀이 코드 🔸

n = int(input())
dp = [i for i in range(n+1)]

for i in range(2,n+1):
    j = 1
    min_v = 4
    while((j**2)<=i):
        dp_v = dp[i-(j**2)]
        min_v = min(min_v, dp_v)
        j+=1
    dp[i] = min_v+1    
print(dp[n])

🔸 코드 해석 🔸

• pypy3 제출
• dp리스트는 0부터 인덱스 n까지 0~n으로 초기화한다. (0, 1만 넣어놔도 됨)
• 2부터 n까지 dp리스트를 채워 나간다. 
  • min_v : 문제 조건에서 답이 4이하이므로 최대값 4를 초기값으로 둔다
  • j는 1부터 j**2이 i 이하일때까지 dp리스트를 계산하며 최소값을 찾는다.
  • dp[i]에 최소값 + 1을 넣는다.

 

🔸 브루트 포스  풀이 코드 🔸

def solution(n):
    if int(n**0.5) == n**0.5:
        return 1
    for i in range(1, int(n**0.5) + 1):
        if int((n - i**2)**0.5) == (n - i**2)**0.5:
            return 2
    for i in range(1, int(n**0.5) + 1):
        for j in range(1, int((n - i**2)**0.5) + 1):
            if int((n - i**2 - j**2)**0.5) == (n - i**2 - j**2)**0.5:
                return 3
    return 4


n = int(input())
print(solution(n))

🔸 코드 해석 🔸

• python3 제출
• 제곱근 (n**0.5)이 정수인지 확인한다. (int()함수에 넣었을때와 값 비교)

---

🔸 end 🔸

• 상당히 어려웠던 문제였다. dp 규칙을 찾는것도 어려웠고 브루트포스 태그도 있어서 혼란스러웠던 것 같다.
  • 결국 검색으로 dp 풀이 포스팅과 브루트포스 풀이 포스팅을 모두 찾아봤지만, 문제를 꼼꼼히 이해하려 노력했다.
• dp는 pypy3로 통과되어서 python3로 통과하는 코드를 찾다가 브루트포스 풀이를 보게되었다.