백준 1699 제곱수의 합

2017.11.02 ** 목요일 ** Solution - 1699(제곱수의 합)
백준 1699 제곱수의합

풀이방법: 동적계획법

엄청 시간이 걸렸던 문제다.

처음에 생각했던 것은 d[2-1] = d[1]+1.. 이런식으로 했었다.

그런데 여기서 4=2의 제곱이 되니 카운트가 바껴야 하는데 그 포인트를 못구했다.

그래서 중간에 월드시리즈 7차전을 잠깐보고 다시 문제를 풀었다.

오늘따라 다저스 타자들이 힘이 없어 보였다..나처럼 ㅜ

풀이방식

한번 생각해보자 ,

처음에 생각했던 방식 d[N - (N-1)] = d[N-1]+1 에 대해서 한번더 생각해보았다.

이렇게 하다보면 d[4]일때가 1차적으로 문제가 생기는데 ,

d[4-4] = d[0]+1을 만들어 줘야하기 때문이다.

자세히 식을 들여다보니 4 =2*2 가 된다. 그렇다면 1은 1x1이 된다는 것을 알 수 있다.

이제 반복문에 대해서 생각을 해보았다.

먼저 우리는 동적계획법을 할꺼고 bottom-up 방식을 사용하기 때문에 1부터 n까지 계산을

해줘야 된다.

for(int i = 1; i < n+1; i++) 로 시작하여

for(int j = 1l; j*j<i; j++)를 만든다. jxj < i 가 포인트인데 이유는

이렇게 하면 2의 제곱은 4부터 등장하게 되고, 처음 방식을 하면서 문제였었던 8은

d[8-4] = d[4] +1 = d[0] +1 +1 = 2가 될 수 있다.

따라서 조건에 의해 제곱수의 범위를 잘 나눌 수 있다. (손으로 해보는 것을 추천한다.)

점화식은 간단하다.

d[i] = Math.min(d[i],d[i-j*j]+1)

여기서 답을 놓칠뻔했다.

왜냐하면 d[i]를 초기화 해주지 않았다. d[i]의 초기화는 모두 d[i]=i로 해야된다.

이유는 모든 수는 1의 제곱으로 구성되어있기때문에, 1의 개수가 최대 개수가 된다.
코드 전체 보기

: 알고리즘은 항상 어렵다.