www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 아이디어: 배낭 문제 dp[i][k] = 최대 배낭 수용 무게가 k일때, i번째 까지의 물건을 봤을 때 가치의 최대합 i번째 물건을 넣을 수 있는 경우(k>=wi): max(dp[i-1][k-wi]+vi, dp[i-1][k]) i번째 물건을 넣을 때 vs 넣지 않을 때 가치가 더 큰 것 선택 i번째 물건을 넣을 수 없는 경우(k dp[n][k] ..
알고리즘💻/DP
www.acmicpc.net/problem/14494 14494번: 다이나믹이 뭐예요? (1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=1e9+7)로 나눈 나머지를 출력한다. www.acmicpc.net 아이디어: "오른쪽, 아래쪽으로만 움직일 수 있을 때, D[1][1]에서 D[x][y]까지 도달하는 경우의 수를 구하는 문제는 일일히 모든 경우를 다 계산할 필요 없이, D[i][j] = (i, j)에 도달하는 누적 경우의 수 = D[i-1][j] + D[i][j-1]를 세워서 해결할 수도 있죠." 문제에서는 →, ↓, ↘의 세 방향을 사용하므로 dp[i][j] = dp[i][j-1] + dp[i-1][j] +..
www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 문제 제목이 이게 무슨 개소리야;; 왠지 좆같은데.. 한남 냄새가 나.. 아이디어: 1과 5로만 구성된 N자리 양의 정수 중, 15의 배수가 몇 개인지 15의 배수: 일의 자리는 0 or 5여야 하므로 일의 자리는 무조건 5, 각 자리의 합이 3의 배수여야 함. 5가 사용된 갯수 i에 따라 (1~N) 각 자릿수의 합을 구할 수 있음. -> 3의 배수인지 확인, 조합 이용(n-1Ci-1) import sys n = int(sys.stdin.readline()) ans = 0 #조합 구하기 N=n-1 dp =..
www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 아이디어: 조건: X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. dp[i] = min(dp[i-1], dp[i//3], dp[i//2]) #i가 3,2로 나누어 떨어지는 경우.. dp[1]=0, dp[2]=dp[3]=1 n까지 bottom-up 방식으로 반복문을 이용하여 구현하였다. import sys n = int(sys.stdin.readline()) dp = [0]*(1000001) dp[2]=1 dp[3]=1 for i in range(4,n+1): a = i%3..
www.acmicpc.net/problem/1757 1757번: 달려달려 어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정 www.acmicpc.net 아이디어: DP를 구성하는 방법을 떠올리는 방식이 어렵다. 조건 - 1분을 달리면 지침 지수는 1이 올라간다. 1분을 쉬면 지침 지수는 1 내려간다. -> 지침지수가 0일 때 쉬어도 그대로 0이다. - 쉬기 시작하면 지침지수가 0이 되기 전에는 다시 달릴 수 없다. - 달리기가 끝나면 지침지수는 0이 되어야 한다. -> 마지막 n분째에는 달릴 수 없다. DP[x][y][z] = x초에 y의 지침지수를 가지고 z는 뛰고 있..
www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 아이디어: DP를 활용하여 생각해보면 1, 2, 3으로 나눌 수 있으므로 i 번째 숫자 = i-1번 숫자에서 1을 더한 경우 + i-2번 숫자에서 2를 더한 경우 + i-3번 숫자에서 3을 더한 경우 로 구할 수 있다. 따라서 dp를 만들어서 dp[i] = dp[i-1]+dp[i-2]+dp[i-3] 으로 푼다. 틀린 부분: 앞선 피보나치 문제처럼 재귀함수를 만들어서 풀 수 있지 않을까 하고 구현해보았는데 시간 초과가 났다. #시간초과 import sys sys...
www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 아이디어: DP의 기본 문제 DP의 핵심은 부분 문제로 나누는 것 + Memorization 일반적인 재귀함수로 풀면 이미 계산한 것을 또 다시 계산해야 하는 비효율성 발생 -> 계산한 값을 저장하는 배열을 만들어 활용! import sys n = int(sys.stdin.readline()) dp = [-1 for _ in range(n+1)] def solve(n): if..
