Programming [Python] (411) 썸네일형 리스트형 #130 백준 파이썬 [2579] 계단 오르기 - 점화식 https://www.acmicpc.net/problem/2579 #Solution 계단 n에 오르는 방법의 수는 2가지 밖에 없다. 이 또한 점화식이다. 1) n-3 --> n-1 --> n 경우 2) n-2 --> n 경우 따라서 저 경우 속의 최댓값만 지속적으로 갱신해주면서 for문을 돌리면 된다. stairs = int(input()) stair_list = [0] result = [[0, 0] for _ in range(stairs + 1)] for _ in range(stairs): stair_list.append(int(input())) for i in range(1, stairs + 1): if i == 1: result[1][0] = stair_list[1] elif i == 2: res.. #129 백준 파이썬 [2293] 동전 1 - 점화식 https://www.acmicpc.net/problem/2293 #Solution result[10]은 결국 result[9] + result[8] + result[5]의 값이다. 피보나치 수열과 같은 점화식이며 다이나믹 프로그래밍으로 풀어야 시간을 줄일 수 있다. n, k = map(int, input().split()) coin_list = [] for _ in range(n): coin_list.append(int(input())) result = [0 for _ in range(k+1)] result[0] = 1 for i in coin_list: for j in range(i, k + 1): result[j] += result[j-i] print(result[k]) #128 백준 파이썬 [1149] - 점화식 https://www.acmicpc.net/problem/1149 #Solution 다이나믹 프로그래밍을 활용해 n-1까지의 RGB 최솟값을 구해준다. 그 뒤 n번째 집을 합했을 때의 최솟값을 구하면된다. n-1과 n만 필요한 점화식이다. house = int(input()) result = [[0, 0, 0] for _ in range(house)] R_list = [0 for _ in range(house)] G_list = [0 for _ in range(house)] B_list = [0 for _ in range(house)] for i in range(house): R, G, B = map(int, input().split()))) R_list[i] = R G_list[i] = G B_list.. #127 백준 파이썬 [9461] 파도반 수열 - 점화식 https://www.acmicpc.net/problem/9461 #Solution 피보나치 수열이 2항의 점화식이라면, 파도반 점화식은 5항의 점화식이다. def padovan(i): if i == 1 or i == 2 or i ==3: return 1 elif i == 4 or i == 5: return 2 else: answer = 0 temp_1 = 1 temp_2 = 1 temp_3 = 1 temp_4 = 2 temp_5 = 2 for j in range(6, i + 1): answer = temp_5 + temp_1 temp_1 = temp_2 temp_2 = temp_3 temp_3 = temp_4 temp_4 = temp_5 temp_5 = answer return answer case =.. #126 백준 파이썬 [1912] 연속합 https://www.acmicpc.net/problem/1912 #Solution 다음과 같은 알고리즘으로 최댓값을 구할 수 있다. 1) 왼쪽부터 더한 값과 현재 값 중의 max값 2) 현재까지의 최댓값과 result 중의 max값 이와 같은 알고리즘은 중간중간 최댓값을 계속 갱신해준다는 장점이 있다. 중간에 음수가 끼었지만 최댓값이 되는 경우의 수를 고려할 수 있다. 또한 시간 복잡도를 O(n) 안에 끝낼 수 있다. n = int(input()) num_list = list(map(int, input().split())) temp = [0 for _ in range(n)] result = -1001 for i in range(n): temp[i] = max(temp[i-1] + num_list[i],.. #125 백준 파이썬 [1463] 1로 만들기 - 점화식 https://www.acmicpc.net/problem/1463 #Solution 점화식을 이용해푼다. f(x)는 다음과 같은 값에서 최솟값을 가진다. 1) f(x-1) + 1 2) f(x/2) + 1 3) f(x/3) + 1 이 세 함수의 최소 값을 구해주면 된다. 재귀함수를 매번 호출하면 시간복잡도가 굉장히 커지므로 다이나믹 프로그래밍 즉, 리스트를 만들어 값을 매번 저장해주는 것이 속도 향상에 도움이 된다. N = int(input()) result = [0 for _ in range(N + 1)] for i in range(1, N + 1): if i == 1: result[i] = 0 continue result[i] = result[i-1] + 1 if i % 3 == 0 and result.. #124 백준 파이썬 [1037] 약수 https://www.acmicpc.net/problem/1037 #Solution N = int(input()) gcd_list = list(map(int, input().split())) gcd_list = sorted(gcd_list) answer = 0 for i in range(len(gcd_list)): answer += gcd_list[i] * gcd_list[-i-1] print(answer//len(gcd_list)) #123 백준 파이썬 [5086] 배수와 약수 https://www.acmicpc.net/problem/5086 #Solution x, y = map(int, input().split()) while (x, y) != (0, 0): if x % y == 0: print("multiple") elif y % x == 0: print("factor") else: print("neither") x, y = map(int, input().split()) 이전 1 ··· 33 34 35 36 37 38 39 ··· 52 다음
