목록전체 글 (217)
Study hard
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..
www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i][j] : i번째 장부터 j번째 장까지 어떤 순서로 합쳐야 최소비용이 나오는지(그 때의 최소비용) Sum[i] : 1장 ~ i장 비용 합 점화식 DP[i][[j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + Sum[j] - Sum[i-1]) (여기서 Sum[j] - Sum[i-1]은 i~j번째 장을 최종으로 합칠 때 드는 비용,..
www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. 중복을 피하기 위해 오름차순으로만 더한다. DP[i][1]: 정수 i를 만들 때 1로 끝나는 경우 -> 그 이전에 1만 올 수 있다. DP[i][2]: 정수 i를 만들 때 2로 끝나는 경우 -> 그 이전에 1과 2가 올 수 있다. DP[i][3]: 정수 i를 만들 때 3으로 끝나는 경우 -> 그 이전에 1과 2..
acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net [풀이] 팰린드롬이란 수열이 거꾸로 했을 때도 같은 수열인 경우를 말한다. 가장 작은 단위의 수열(1개)부터 범위를 늘리면서 팰린드롬 여부를 판단하는 DP를 사용하였다. DP[i][j]: S가 i이고 E가 j일 때 팰린드롬인지 여부 DP[i][i] = 1 if Num[i]==Num[j] : DP[i][i+1]=1 DP[i][j] = DP[i+1][j-1] && Num[i] == Num[j] ※cin, cout을 사용하면 시간초과가 나므로 scanf, pri..