풀이방법: 동적계획법
엄청 시간이 걸렸던 문제다.
처음에 생각했던 것은 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의 개수가 최대 개수가 된다.
코드 전체 보기
: 알고리즘은 항상 어렵다.
'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글
| 백준 2579 계단오르기 (0) | 2017.11.07 |
|---|---|
| 백준 1463 1로 만들기 (0) | 2017.11.03 |
| 백준 11726,11727 2xN타일링 , 2xN타일링2 (0) | 2017.11.03 |
| 백준 11051 이항 계수2 (0) | 2017.11.01 |
| 백준 1915 가장 큰 정사각형 (0) | 2017.11.01 |
