키큰개발자

객체지향 분석 설계 (Objet-Oriented Analysis & Design)

- 고객이 원하는 것을 하고 잘 설계되었다라는 것을 보장하는 소프트웨어 개발 방법

- 다음 순서로 개발하면 잘 만든 소프트웨어라고 말할 수 있다고 한다.

1. 원하는 것을 충분히 잘 들어준다. -> 요구사항 (잘)만들기

2. 유연하게 만든다. -> 객체지향 원리 적용

3. 좀 더 유연하고, 좀 더 확장성있고, 좀 더 유지보수하기 쉽게 바꾼다. -> 객체지향 원리 적용 + 디자인 패턴 

대부분 사람들이 이런 메세지가 뜨면 45일 이용을 못한다고 한다.

하지만 사실과는 전혀!!! 다르다.

나 또한 그런줄 알았지만 저기 저 문구 대로 고객센터에 문의를 해보고 답변을 잘하게 되면 1주일 내? 로 풀릴 수도 있다. 

하지만 문의조차 귀찮타라고 하면 걍 45일 기다리면된다 아니면 번호를 바꾼다거나?? 

암튼 모든 자기 하기에 따라 결과가 바껴지는듯~~

문제 링크 : https://www.acmicpc.net/problem/1699

해결 방법 :

이 문제는 다이나믹 프로그래밍 문제다.

그렇기 때문에 먼저,

우리가 구하고자 하는 문제가 뭔지 본다. 

문제는 주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수 이다. 

ex) N = 3  , 1^2 + 1^2 + 1^2 = 3개 

    N = 7,  3^2 + 1^2 + 1^2 = 3개

나는 처음에 접근한 방법이 제곱을 했을때 (N 과 가장 가까운 수에 대해 최소항의 개수  + N- 가장가까운수 에대한 최소항의 개수) 로 점화식을 세워서 풀었었다. 하지만 이는 12를 구할때 깨져버린다. 

위점화식을 적용해보면, 9의 최소항의개수 + 12-9의 최소항의개수 = 4가 나오게 된다.

2^2 + 2^2 + 2^2 = 3개 이것이 최소개수인데 말이다. ㅜㅜ

다시 생각해 본 후 , 모든 경우를 고려하면 답을 구할수 있다고 봣다.

즉, 어떤 수 12는  제곱의 합에서 1의 제곱이 포함됬다고 보면 11의 최소항의개수 + 1 이 될것이다. 여기서 +1 은 1의 제곱이 포함됬기 때문이다.

12는 또 제곱의 합에서 2의제곱이 포함됬다고 보면 10의 최소항의 개수 + 1 이 된다.

12는 또 제곱의 합에서 3의 제곱이 포함됬다고 보면 9의 최소항의 개수 + 1이 된다.

이렇게 모든 경우를 포함하는 점화식을 세운다면 DP[N] = MIN ( DP[N], DP[N-j의제곱] + 1)  이될것이다.

(이때, j는 제곱해서 N보다 같거나 작을때까지의 수를 반복해서 도는 경우이다.)