Study hard

www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[x]: 가치의 합 x를 얻기 위해 사용한 동전의 최소 개수 점화식 if coin[i]

www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[x] : 가치의 합이 x가 되는 경우의 수 점화식 if coin[i] k; for (int i = 1; i > coin[i]; } cout

www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net [풀이] 재귀 DP로 풀 수 있는 문제였다. DP[x]: 길이 x인 올바른 괄호 문자열의 개수 #include #include using namespace std; int T, L; long long DP[5001]; long long solution(int len) { //길이가 0이 될 때까지 재귀 돌렸으면 if (len == 0) return 1; long long& res = DP[len]; //이미 ..

www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net [풀이] 재귀 DP로 풀 수 있는 문제였다. DP[x][y][z] : 체력이 각각 x,y,z인 SCV 파괴하기 위한 공격 횟수의 최솟값 해당 SCV가 없거나 파괴되었으면 0으로 두고 풀면 된다. #include #include //min #include //memset using namespace std; int N; int DP[61][61][61]; int HP[3] = { 0, };//SCV없으면 그냥 0 int ..

www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i][j] : i번째 곡을 j 볼륨으로 연주 가능한가?(boolean) 점화식 if DP[i][j] AND j+V[i] = 0 : DP[i+1][j-V[i]] = true #include #include //max using namespace std; int N, S, M; int V[101]; bool DP[101][1001];..

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로 풀 수 있는 0-1 Knapsack문제였다. DP[i]: 용량이 i만큼 남았을 때 배낭에 넣을 수 있는 아이템 가치의 최댓값 점화식 if W[i] < K : DP[j] = max(DP[j], DP[j-W[i]]+V[i]) 지금까지의 용량 j일 때의 최댓값과 i번째 아이템을 추가 했을 때의 값을 비교 #include #include..