[BOJ][Python]17626번 풀이
https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net import math t = [0 for _ in range(50001)] t[0],t[1],t[2],t[3]=0,1,2,3 for i in range(4,50001): minv=5 a = math.floor(math.sqrt(i)) for j in range(1,a+1): minv = min(minv, t[i-j**2]+1) t[i] = minv print(t..
2022. 6. 7.
[BOJ][Python]15489번 풀이
https://www.acmicpc.net/problem/15489 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net t = [[0 for _ in range(31)] for _ in range(31)] t[1][1] = 1 for i in range(2,31): for j in range(1,31): t[i][j] = t[i-1][j-1] + t[i-1][j] r,c,w = map(int, input().split()) answer = 0 for i in range(w): for j in range(i+1): answer += t..
2022. 6. 4.
[BOJ][Python]14916번 풀이
https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net t = [-1 for _ in range(100001)] t[2],t[4],t[5],t[6],t[7],t[8] = 1,2,1,3,2,4 for i in range(9,100001): t[i] = min((t[i-2]+t[2]),(t[i-5]+t[5])) print(t[int(input())]) 이번에도 평이한 난이도의 문제입니다만 생각을 어떻게 하는지에 따라 결론에 다다르는 시간이 다를 것 같네요. 일단 가장 적은 갯수의 동전을 반환하기 위해서는 뭐가 됐든 숫자가 늘 때 1개만 늘어나는게 가장 바람직한 일이죠. 따라..
2022. 6. 2.