n = int(input()) dp = [0, 1, 2] if n >= 3: for i in range(3,n+1): next = dp[i-1] + dp[i-2] dp.append(next) print(dp[n] % 10007) 이번 문제의 규칙을 찾다보면 피보나치 수열을 따른다는 것을 알 수 있다. 이것만 찾으면 큰 무리 없이 구할 수 있는 문제다. n = 2 n = 3 n = 4 n = 5 n = 6

m = int(input()) result = [] for _ in range(m): n = int(input()) dp = [0, 1, 2, 4] if n >= 4: for i in range(4, n+1): nextDP = dp[i-1] + dp[i-2] + dp[i-3] dp.append(nextDP) result.append(dp[n]) for i in result: print(i) Idea 규칙을 찾는 것이 Point 1, 2, 3 만으로 연산을 하여 해당 숫자를 만들 수 있는 경우의 수를 구해야했기 때문에 아래처럼 규칙이 나타났다. A(n) = A(n-1) + A(n-2) + A(n-3) A(1) A(2) A(3) A(4) A(5) A(6) 1 1+1 1+1+1 (A(2)+ 1) 1+1+1+1..

조건 X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. Idea DP (Bottom-Up 방식) : 결과 저장용 리스트인 DP 테이블을 통해 1부터 N까지 순차적으로 1을 만들기 위한 최소 연산 횟수를 저장 # 여기서 만든 로직은 제일 작은 수인 1부터 순차적으로 최소 연산 횟수로 1을 만드는 방법을 저장하면서 N까지 도달하는 것 N = int(input()) dp = [0] * (N+1) # 1은 아무런 연산을 하지 않아도 되므로, 2부터 시작 for i in range(2, N+1): # +1 = 일단 -1 연산을 했을때의 경우를 카운팅한 것 dp[i] = dp[i-1]+1 # -1 연산을 한 경우와 3 으로 나누는 경우 중에서 횟수가 더 적은 것을..

동적계획법 (DP : Dynamic Programming) 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 수행시간의 비약적 향상이 핵심으로 '메모이제이션'이라는 기법을 사용해 이미 계산된 결과는 별도의 메모리에 저장하여 필요한 경우 다시 계산하지 않고 다시 꺼내 사용하는 방식 Top-Down 방식 : 메모이제이션을 통한 재귀함수를 사용한 방식 Bottom-Up 방식 : 결과 저장용 리스트인 dp 테이블을 통해 반복문으로 문제를 해결 N = int(input()) T = [] P = [] dp = [] for _ in range(N): t, p = map(int, input().split()) T.append(t) P.append(p) dp.append(p) dp.append(0) for i in range..

import math N = int(input()) A = input().split(' ') B, C = map(int, input().split()) cnt = 0 for i in A: i = int(i) - B cnt += 1 if i > 0: cnt += math.ceil(int(i) / C) print(cnt) N = 시험 장소의 수 A = 각 시험장에 있는 학생의 수 B = 감독관이 감독할 수 있는 최대 학생의 수 C = 부감독관이 감독할 수 있는 최대 학생의 수 문제 Key Point 시험 장소에는 1명의 감독관이 무조건 존재해야한다. (2명 이상의 감독관이 들어갈수는 없음) 따라서 감독관이 감독 가능한 학생의 수가 초과되면 나머지 학생들은 부감독관이 감독

문제 설명 원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다. ex) 1일때는 오른쪽 위로 이동 그림을 그릴 때, 사방이 막히면 방하나로 샙니다. 이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요. 제한사항 배열 arrows의 크기는 1 이상 100,000 이하 입니다. arrows의 원소는 0 이상 7 이하 입니다. 방은 다른 방으로 둘러 싸여질 수 있습니다. 입출력 예 arrows return [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 입출력 예 설명 (0,0) 부터 시작해서 6(왼쪽) 으로 3번 이동합니다. 그 이후 주어진 a..