728x90 DP16 [python] 백준 17626 Four Squares https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 해결 n보다 작은 수의 제곱수의 개수를 연결하는 것이므로 dp를 이용하는 것이 좋겠다는 생각을 하게 된다. 시간제한이 0.5초이기 때문에 빡세다. (python3로는 계속 탈락... pypy3로 풀었는데 python3까지 최적화를 못시키겠다.) 1 = $1^{2}$ 이므로 dp[1] = 1 dp[0] = 0으로 고정한다. 2부터는 for문을 통해 알아갈 것.. 2023. 3. 14. [python] 백준 2011 암호코드 https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제 해결 각 자리수 숫자를 분석해야한다. 알파벳으로 바꿀 때 해석의 가지수에 영향을 주는 것은 바로 앞에 수 하나이다. 하나씩 분석해서 이전의 수와 연결해서 10이상 26이하가 나오면 다른 암호로 해석할 여지가 있다. DP를 이용할 것이다. DP[i]는 i번째 수까지 봤을 때 해석의 가지수이다. 바로 앞에 수와 독립적으로 해석하는 가지수는 dp[i-1]이고 연결해서 해석하는 가지수는 dp[i-2]이다. CODE .. 2023. 3. 14. [python] 백준 1965 상자넣기 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 문제 해결 이전의 상자들이 영향을 주기 때문에 dp 이용해야 한다는 느낌이 든다. 하지만 어느 상자를 마지막에 넣어야 할 지는 잘 알 수 없다. 마지막에 넣을 수 있는 상자의 인덱스를 미리 알아본다. (for문을 통해) dp[i]를 i상자 안에 있는 최대 상자 개수라고 하면 for문을 통해 i보다 작은 인덱스 상자 중 넣을 수 있는 상자 최대 개수와 dp[i]를 비교해가며 최댓값으로 dp[i]를 수정해간다.. 2023. 3. 12. [python] 백준 1937 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제 해결 계속해서 그래프 안을 상하좌우 움직이고 갔단 곳은 안가므로(숫자가 증가 수열이므로) DFS 사용하는 것이 좋을 것이다. 그런데 그냥 쓰면 당연히 시간초과가 날 것이다. 이전에 방문해서 결과를 냈던 것은 저장을 하는 것이 필요하다. 그러기 위해서는 dp를 사용해서 이전에 (r,c) 좌표에서 DFS 시작했을 때 최댓값이 dp[r][c] 였다.라고 저장되어있으면 넘어간다. CODE.. 2023. 3. 10. 이전 1 2 3 4 다음 728x90
