백준 DP에 관한 문제입니다.

Question

https://www.acmicpc.net/problem/1699에서 제가 푼 풀이는 using System; using static System.Console; public class main { static int[] dp; static void Main() { int n &#61; Convert.ToInt32(ReadLine()); dp &#61; new int[n &#43; 1]; WriteLine(SqrtSum(n, 0)); } static int SqrtSum(int n, int count) { if (dp[n] !&#61; 0) return dp[n]; if (n < 4) return count &#43; n; int start &#61; (int)Math.Sqrt((double)n); int min &#61; Int32.MaxValue; for(int i &#61; start; i > 1; i--) min &#61; Math.Min(min, SqrtSum(n - i * i, count &#43; 1)); dp[n] &#61; min; return dp[n]; } } 이렇습니다. 1~20, 142, 1000, 10000, 99999 등 다 맞는데 4%에서 자꾸 틀리다고 나옵니다.DP를 쓰는 게 잘못됐다거나, 그냥 알고리즘 자체에 문제가 있다거나 같은 어디가 틀렸는지 알려주시면 감사하겠습니다.

스토리 · Answer

일단.. 이런 건 백준 가서 물어보셔도 됩니당. 1~100까지 출력해도 특정 수 이상으로 1이 계속해서 나옵니다. 예를 들어 99의 제곱수의 합이 1인 건 말이 안되니 알고리즘 자체가 잘못 됨을 알 수 있습니다. 먼저 더할 수 있는 최대 개수의 설정의 경우, 그리고 SqrtSum 재귀를 할 때 개수를 더 해주지 않는 점이라고 생각 되네요. count 매개변수는 왜 쓰이는 지 모르겠어요. 재귀의 종료 조건도 이해가 안갑니당

백준 DP에 관한 문제입니다.

1개의 답변

#dp 목록