5557번: 1학년 (acmicpc.net) 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 해당 문제는 다이나믹 프로그래밍으로 해결하였습니다. 도무지 생각해도 아이디어가 안 떠올랐다. 고민하다가 hint를 보게 되었는데 8+3-2-4+8-7-2-4-0+8=8 8+3-2-4+8-7-2-4+0+8=8 8+3+2+4-8-7+2-4-0+8=8 8+3+2+4-8-7+2-4+0+8=8 8+3+2-4+8-7+2+4-0-8=8 8+3+2-4+8-7+2+4+0-8=8 8-3+2+4-8+7+2+4-0-8=8 8-3+2..
2294번: 동전 2 (acmicpc.net) 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 해당 문제는 다이나믹 프로그래밍으로 문제를 해결하였습니다. 예제는 3가지의 동전{1, 5, 12} 과 15원을 만드는데 최소 동전 수를 구하는 문제입니다. 1-> 1 dp[1] = 1 2 - > 1, 1 dp[2] = 2 3 -> 1, 1 , 1 dp[3] = 3 4 -> 1, 1, 1, 1 dp[4] = 4 5 - > 1, 1, 1, 1, 1 dp[5] = 5 or 5 위 예시에서 동..
9084번: 동전 (acmicpc.net) 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 다이나믹 프로그래밍(DP)으로 문제를 해결하였습니다. 간단한 예시로 {1원, 2원, 3원} 3종류의 동전이 있습니다. 0원의 값을 만들기 위해서는 아무것도 사용하지 않는 경우 1가지가 있습니다. 1원의 값을 만들기 위해서는 1원 한 가지의 경우입니다. 2원의 값을 만드는 경우는 1+1, 2 2가지가 있습니다. 3원의 값을 만드는 경우는 1+1+1 , 1+2, 3이 있습니다. 위 그림을 자세히 살펴보면 1..
DFS 깊이우선탐색 방식으로 문제를 해결하였습니다. 주의할 점은 DFS로 내려가면서 자식노드가 없는 리프노드의 경우와 삭제했을 때 생기는 리프노드의 경우를 구분해주어야합니다. 삭제되는 위치에 따라 리프노드의 카운트가 변경되기 때문에,입력한 값의 노드가 삭제되었을 때 해당 DFS를 종료시켜주어야합니다. 리프노드의 카운트를 세는 경우는 왼쪽 자식노드와 오른쪽 자식노드가 없는 경우입니다. 이를 코드로 생각해보면 tree[node].size() == 0가 되겠습니다. 그리고 노드를 삭제했을 때 리프노드가 생기는 경우를 생각합니다. 다른 경우는 부모 노드가 tree[node].size()==1 왼쪽이든 오른쪽이든 자식노드를 하나만 갖고 그 자식노드가 삭제되었을 경우를 생각합니다. 자식 노드를 한개를 갖고있는 부모..
#include #include #include using namespace std; int main(){ priority_queue pq; int N; cin>>N; for(int i = 0; i >temp; if(temp){ pq.push(make_pair(abs(temp), temp)); }else if(!temp){ if(pq.empty()){ cout
#include #include #include using namespace std; priority_queue maxheap; priority_queue minheap; map m; int main(){ int N; int M; int L; int P; int command; cin>>N; for(int i = 0; i >P>>L; m[P] = L; maxheap.push(make_pair(L, P)); minheap.push(make_pair(L, P)); } cin>>M; for(int i = 0; i >command; if(command == "recommend"){ int x; cin>>x; if(x == 1){ ..
