[백준] (Swift) 1699번 - 제곱수의 합 (dp)

문제링크

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

1699번: 제곱수의 합

 

문제 풀이 IDEA

우선 dp 문제를 만나면, 규칙을 파악하기 쉽게 모든 경우의 수를 수기로 써본다.

이렇게 작성해보았다. 문제의 규칙이 보일듯, 보이지 않았다.  dp 배열에 1일때 항의 수 1, 2일때 항의 수 2, 3일때 항의 수 3, 4일때 항의 수 1.. 이렇게 넣으려고 하는 건 알겠다. 근데 이제 어떻게 점화식을 만들어야할까?

우선 나는 아래와 같은 변수들과 배열을 만들것이다.

• 입력받을 n , 항의 수를 넣어놓는 배열 dp, 현재의 수를 지칭하는 i, 제곱근으로 경우의수를 따져볼 j

let n = Int(readLine()!)!
var dp = Array(repeating: 0, count: n+1)

이제 규칙을 찾아보자. 위 예시들 중에서 적당히 2제곱근과 1제곱근이 섞여있는 6을 예시로 들어보자. 6은 2제곱 + 1제곱 + 1제곱으로 3개의 항으로 이루어져있다. 

2제곱은 dp[4] 일때 구성되는 항이고, 1제곱+1제곱은 dp[2] 가 구성될때 나타나는 항이다. 이것을 바탕으로 구할 수 있는 점화식은 다음과 같다.

• dp[6] = dp[4] + dp[2] = dp[2^2] + dp[2]

만약 6이라면, 3^2 은 항을 이룰 수 없다 이점을 활용하여 식을 세워보면, dp[6]을 초기화할때 6 > 2^2 가 되어야한다.이를 if 조건문으로 넣고, 6을 i로, 제곱근을 표현하는 2를 j 로 넣어보자.

for i in 1..<n+1 {
    dp[i] = i
    for j in 1..<i+1{
        // 제곱수가 현재 i 보다 커지면 break
        if i < j*j {
            break
        }
        if dp[i] > dp[i-(j*j)] {
            dp[i] = dp[i-(j*j)] + 1
        }
    }
}

dp[i] = i 를 넣는 이유는, 최대로 이루어질 수 있는 항을 일단 넣어주는 것이다. 우리의 목표는 어차피 최소 값을 구하는 것이기 때문에 최대로 이루어질 수 있는 항을 넣어준 후, 나중에 dp[i]를 초기화 해주는 방식으로 진행했다. (dp[6] = 6 이 되는데, 1^2을 6번 더하는 것이 최대 항의 개수이다.)

그리고 앞에서 예시로 들었던 6 < 3^2 을 첫번재 if 문으로 나타냈다. 6은 3의 제곱 이상으로 이루어질 수 없기 때문에, j로 3을 만나는 순간 for문을 탈출하게 만들었다.

마지막 if 문이 핵심이다. 여기서 dp[i] > dp[i-(j*j)] 를 보자. 왜 이조건이 나왔는가? 우리는 dp[6]을 이루는 최소값을 찾아야 하기때문에, 작은 항의 개수가 나오면 지속적으로 초기화 해주어야 한다. 그래서 현재의 dp[i]가 더 크면 초기화하는 과정을 거치는 것이다.

 

이 모든 소스를 합친 소스코드는 다음과 같다.

 

소스코드

let n = Int(readLine()!)!
var dp = Array(repeating: 0, count: n+1)

for i in 1..<n+1 {
    dp[i] = i
    for j in 1..<i+1{
        // 제곱수가 현재 i 보다 커지면 break
        if i < j*j {
            break
        }
        if dp[i] > dp[i-(j*j)] {
            dp[i] = dp[i-(j*j)] + 1
        }
    }
}

print(dp[n])