전체 글293 [Ch. 8 다이나믹 프로그래밍] 바닥 공사 My code n = int(input()) d = [0] * 1001 d[1] = 1 d[2] = 3 for i in range(3, n + 1): d[i] = (d[i - 1] + d[i - 2] * 2) % 796796 print(d[n]) Code Review 이번 문재는 2 X N 인 직사각형이 있을 때 1 X 2, 2 X 1, 2 X 2 덮개를 이용해 채울 수 있는 경우의 수를 구해보는 것이었습니다. 점화식을 떠올리기 쉽지 않은 문제였습니다. 따라서 그림을 이용하여 경우의 수를 어떻게 구할 수 있을지 생각해보았습니다. 먼저 덮개를 왼쪽부터 채운다고 가정하고 만약 i - 1 번째 까지 타일을 모두 채웠을 때, 2 X 1 덮개로 나머지 부분을 채우는 방법 1가지만 존재합니다. 만약 i - 2 번째.. 2022. 2. 16. [Ch. 8 - 다이나믹 프로그래밍] 개미 전사 My code n = int(input()) k = list(map(int,input().split())) d = [0] * 101 d[0] = k[0] d[1] = max(k[0], k[1]) for i in range(2, n): d[i] = max(d[i - 1], d[i - 2] + k[i]) print(d[n - 1]) Code Review 이번 문제는 일직선으로 이어진 식량 창고가 있을 때 얻을 수 있는 식량의 최댓값을 구하는 것 이었습니다. 단, -서로 인접한 식량 창고는 약탈 할 수 없다 (한 칸 이상 떨어져야 함) 이 문제의 점화식을 세우기 위해서는 위의 조건을 꼭 고려해주어야 합니다. -a(i) = max[a(i-1), a(i-2) + k(i)] 계속해서 구할 수 있는 식량의 최대값을 .. 2022. 2. 16. [Ch. 8 - 다이나믹 프로그래밍] 1로 만들기 My code x = int(input()) d = [0] * 30001 for i in range(2, x + 1): d[i] = d[i - 1] + 1 if i % 2 == 0 : d[i] = min(d[i], d[i//2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i//3] + 1) if i % 5 == 0: d[i] = min(d[i], d[i//5] + 1) print(d[x]) Code Review 이번 문제는 다음과 같은 4 가지 연산을 수행하여 1을 만들 때 연산을 사용하는 횟수의 최솟값을 출력하는 문제였습니다. -x 가 5로 나누어 떨어지면, 5로 나눈다. -x 가 3으로 나누어 떨어지면, 3으로 나눈다. -x 가 2로 나누어 떨어지면, 2로 나눈다. -x 에.. 2022. 2. 16. [Ch.7 - 이진 탐색] 떡볶이 떡 만들기 My code n, m = map(int,input().split()) array = list(map(int,input().split())) start = 0 end = max(array) result = 0 while start mid: total += x - mid if total < m: end = mid - 1 else: result = mid start = mid + 1 print(result) Code Review 이번 문제는 손님이 요청한 떡의 길이가 m 일 때 적어도 m 만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제였습니다. 이 문제는 이진 탐색 알고리즘을 이용하여 해결할 수 있습니다. 먼저 시작 값을 0, 마지막 값을 입력 받은 길이의 최대값으로 설정한 후 .. 2022. 2. 15. 이전 1 ··· 43 44 45 46 47 48 49 ··· 74 다음
