목록Four Squares (1)

JINWOOJUNG

[ DP - 17626 ] Four Squares

문제 접근법 DP 문제이다 직접 해보자. 1 -> 1 -> 1 2 -> 1 + 1 -> 2 3 -> 1 + 1 + 1 -> 3 4 -> 22 -> 1 5 -> 22+1 -> 2 = 1 + DP[5- 22 ] 6 -> 22+1+1 -> 3 = 1 + DP[6-22] 약간 규칙이 보일 것이다. 자연수 N의 제곱으로 표현되는 1,4,9 등은 1개가 최소이다. N의 제곱으로 표현되지 않으면, 나와 가장 가까운 자연수 N의 제곱을 뺀 DP[] 값에 1을 더해주면 된다. 하지만 예외사항이 발생한다. 23의 경우 위 논리데로 수행하면 DP[23] = DP[7] + 1, DP[7] = DP[3] + 1 = 4이므로 DP[23]은 5이 된다. 이는 넷 혹은 그 이하의 자연수의 제곱의..
백준 2024. 4. 2. 00:07
이전 Prev 1 Next 다음