목록백준/DP (47)
Study hard
www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net [풀이] DP를 이용하여 풀 수 있는 문제였다. DP[i] : i번째 눌렀을 때 A의 최대 개수 점화식 DP[0] ~ DP[5]까지는 A를 하나 출력하는 게 최대 DP[i] = max(DP[i-1]+1,DP[i-3]*2,DP[i-4]*3,DP[i-5]*4) ※화면을 선택하여 복..
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];..