코딩하는 드래곤 🐲

[링크] www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net [풀이] DP로 풀 수 있는 문제입니다. 정수 n을 1,2,3으로만 이루어진 숫자의 덧셈으로 만드는 경우의 수를 세면 됩니다. dp 배열은 다음과 같이 정의할 수 있습니다. dp[n][i] => 숫자 n에 마지막으로 더할 숫자로 i를 사용할 때의 경우의 수 예시) 1) dp[3][1]은 숫자 3을 만들기위해 마지막으로 더할 숫자로 1을 사용할 때의 경우의 수입니다. 1+1+1이 가능하므로 dp[3][1] = 1입니다. 2) dp[3][2]은 숫자 3을 만들기위해 마지막으로 더할 숫자로 2를 사용할 때..

[링크] www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 � www.acmicpc.net [풀이] 최대 공부 시간의 크기(10000)와 과목 수의 크기(1000)을 고려하여 DP와 Knapsack 알고리즘을 사용하여 풀 수 있는 문제입니다. 12865: 평범한 배낭 문제와 똑같습니다. 점화식을 정의하면 다음과 같습니다. dp[i][j] = 과목 i를 공부 시간이 j 밖에 없을 때, 중요도의 최대값 1) 현재 과목의 필요 공부 시..

[링크] 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와 Knapsack 알고리즘을 사용하면 되는 문제였습니다. 풀이는 다음과 같습니다. 1. item 구조체 선언 각각의 물건들은 무게(w)와 가치(v)를 가지고 있기 때문에, 해당 데이터를 가지고 있는 구조체를 선언합..