하나씩 알아가기

가장 첫번째 예시를 보면 1을 네 장 사서 4가 되는 것 보다 두장 짜리를 두 번 사서 4를 만드는 것이 4 < 5 * 2 로 금액이 더 큰 것을 알 수 있습니다. 작은 문제로 나눠서 생각하는 것이 중요합니다. 예를 들어 세번째 카드를 구매하면 N개 중 3이 소모되는 것 입니다. 그러면 나머지 N-3개에 대한 dp를 출력하면 됩니다. dp를 갱신시켜나가는데 현재카드와 [N-현재카드의 번호]의 dp값을 비교해서 더 큰 것으로 갱신시키면 됩니다. n = int(input()) card = list(map(int, input().split())) card.insert(0, 0) dp = [0 for _ in range(n+1)] for i in range(1, n+1): for j in range(1, i+1..

입력 받은 수를 제곱수의 합으로 나타낼 때 각 항(반드시 양의 정수의 제곱)의 수의 최소값을 구하는 문제입니다. 수 1 2 3 4 5 6 7 8 ... 항의 개수 1 2 3 1 2 3 4 2 ... DP 테이블을 갱신시켜 나가는데 바깥 루프에서는 dp[i] = i 즉, 그 수 만큼의 값으로 채워주고 이것이 최댓값입니다. 안쪽 루프에서는 더 작은 횟수로 줄일 수 있을 때 갱신 해 나갑니다. dp[i] = min(dp[i], dp[i-j**2] + 1) 이것이 가장 핵심이 되는 구문인데 이 식을 생각해 내는것이 정말 어려운 것 같습니다. 여기서 +1을 해주는 이유는 어떤 수든지 최소 한 개의 항으로는 나타내야 하기 때문입니다. 즉 dp[x] = 0 은 불가능합니다. 1부터 시작합니다. n = int(inpu..