https://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 🔔 문제 : (1> k; vector dp(n + 1, vector(k + 1, 0)); vector v(n+1); for (int i = 1; i > v[i].first >> v[i].second; } for (int i = 1; i

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 🔔 문제 : (1 n >> m; int dest = n * m; vector dp(dest); for (int i = 0; i > tmp; int idx = i * m + j; if (i == 0 && j == 0) dp[idx] = tmp; else if (i == 0) dp[idx..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 🔔 문제 : 이친수의 개수를 출력하는 문제입니다. 🔔 Kick Point : DP 문제이고, 0의 개수에 집중하면 됩니다. F(x) 가 x의 0의 갯수라고 생각하면 F(k) = 2* F(k-2) + F(k-3) 이라는 식이 나옵니다. 또한 G(x)가 x의 이친수의 갯수라고 생각하면 G(x) = F(x+1) 이라는 식을 알 수 있습니다. 이는 G(k) = G(k-1) + G(k-2) 라는..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 🔔 문제 : (1 k; vector coin(n); vector dp(k + 1, 10001); dp[0] = 0; for (int i = 0; i > coin[i]; } // O(n*k) Bottom-up for (int j = 1; j = 0) && (dp[j-coin[i]] != -1) ) { min = (min > dp[j - c..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔔 문제 : (1 k; vector v(n); vector dp(k + 1); for (int i = 0; i > v[i]; } dp[0] = 1; for (int i = 0; i < v.size(); i++) { for (int j = v[i]; j

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 🔔 문제 : 정수 X에 3가지 연산만 사용할 수 있습니다. 1. X가 3으로 나눠지면, 3으로 나눌 수 있습니다. 2. X가 2로 나눠지면, 2로 나눌 수 있습니다. 3. 1을 뺍니다. 정수 X이 주어졌을 때, 연산을 사용하는 횟수의 최솟값을 출력하는 문제입니다. 정수는 1보다 크거나 같고, 10^6 작거나 같은 정수 입니다. 🔔 Kick Point : DP문제입니다. O(n)의 시간 복잡도로 해결을 하며, Bottom up 방식으로 풀 것이고 1씩 더하는 조건을 기본 디폴트로 둡니다. 즉 F(n) 일 때, m..

https://www.acmicpc.net/problem/23972 23972번: 악마의 제안 첫째 줄에 악마가 제안한 정수 K와 N이 공백을 사이에 두고 주어진다. (1 ≤ K, N ≤ 200,000,000) www.acmicpc.net 🔔 문제 : (1= X (N-1)X >= K*N X >= (K*N)/(N-1) 즉 (K*N) / (N-1)일 보다 큰 정수의 X값을 구하는 문제입니다. 여기서 (K*N) / (N-1) 값이 소수점이 있는 경우 +1을 해주면 정수값이 되고, (K*N) / (N-1) 소수점이 없는 경우는 그냥 그 값 그대로 해주면 됩니다. 이거를 (k*n)%(n-1)으로 판별 할 수 있었습니다. 참고로 꼭 삼항조건식을 사용할 때, () 괄호로 묶어줘야지 오류가 안나고 잘 사용됩니다! 🔔 ..

https://www.acmicpc.net/problem/14910 14910번: 오르막 첫째 줄에 공백으로 구분된 N(1 ≤ N ≤ 1,000,000)개의 정수가 주어진다. 입력으로 주어지는 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 🔔 문제 : (1