알고리즘
백준 #1699 <제곱수의 합>
난이도 : 실버2소요시간 : 48m사용한 풀이법 : DP풀이 과정dp용 리스트 선언각 인덱스에는 1로만 표현했을경우의 개수를 넣는다. 즉, 인덱스 번호를 그대로 대입!루프를 돌면서 DP탐색 시작인덱스 번호보다 작은 제곱 수 중에서 가장 큰 값을 찾는다.현재 인덱스 번호에서 해당 제곱 수를 뺀 인덱스 번호에 +1을 한 후, 대소비교를 진행한다.ex) dp[10] = dp[10-33]+1 = dp[1]+1 (11 + 3*3, 2개!)+1을 하는 이유는 앞선 dp[]값에 제곱 수의 경우가 하나 추가되는 것이기 때문작성 코드import mathN = int(input())dp = [x for x in range(N+1)]for i in range(1, N + 1): for j in range(1, int(..
2024. 3. 9. 00:00