DP

17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 의식의 흐름 dp로 1~n까지 만드는데 필요한 최소 개수 구해보자. + 종이에 1~12까지 구할 수 있는 최소 경우의 수를 써보는데 12 = 3^2+1^2+1^2+1^2(4개) / 2^2+2^2+2^2(3개)로 나뉘는 것을 확인하고 무조건 최대 제곱수를 쓰면 틀리겠구나 생각함 풀이 과정 1. 자연수(n)을 입력받는다. 2. 1~n까지 만드는데 필요한 제곱수의 최소 개수를 구하여 배열(dp)에 저장한다. dp[i] = i를 만드는..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 의식의 흐름 dp 문제네 -> 0원~n원까지 가능한 경우의 수를 다 저장하면 되겠다. -> 풀고 나니 1,000,000,007로 나눈 나머지라는 조건을 까먹고 그냥 원래 값을 return했는데 통과네..? -> 1,000,000,0007로 나누는 코드 추가해서 제출했는데 시간 초과 🙄 -> 코드 살짝 수정하고 통과 문제 자체는 어렵지 않았는데 이 문제 덕분에 내가 쓰던 로직을 살짝 수정해서 좀 더 빠른 로직으로 수정할 수 있었다 풀이 과정 1. i번째 동전까지 사용해서 j원 만들 수 있는 경우의 수를 담을 배..