jmmm_25

출처: www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 위 문제는 분할 정복 문제이다. 분할 정복 알고리즘 문제는 처음 풀어보긴 해서, 어떻게 접근할지 몰라 구글링의 힘을 빌렸다. 2번에서 같은 크기의 9개의 종이로 자르고 --> 이 부분을 통해 분할 정복임을 알 수 있다. 풀이의 경우에는 이중 for문과 배열 시작/종료 지점에 대해서만 잘 생각한다면 금방 풀 수 있는 문제이다. 전체 소스: github.com/jmmm25/Algorithm/blo..

문제 출처: www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net C++ STL의 최대힙 priority_queue를 통해 쉽게 해결할 수 있는 문제이다. Max Heap의 개념 - 최대 트리(Max Tree)는 각 노드의 키(Key)값이 (자식 노드가 있다면) 그 자식의 키(Key)값보다 작지 않은(=크거나 같은) 트리이다. - 최대 힙(Max Heap)은 최대 트리(Max Tree)이면서 완전 이진 트리(Complete Binary Tree..

출처: www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 주어진 수를 적절하게 순서를 변경하여 최대 or 최소 값을 구하는 문제는 순열을 통해 문제 해결을 하면 된다. C++ STL의 next_permutation 함수를 통해 쉽게 문제를 해결할 수 있다. 전체 소스 보기 : github.com/jmmm25/Algorithm/blob/master/BOJ/10819.%20%EC%B0%A8%EC%9D%B4%EB%A5%BC%20%EC%B5%9C%EB%8C%80%EB%A1%9C/m..

문제출처: www.acmicpc.net/problem/1541 위 문제는 주어진 식에 괄호를 적절히 쳐서 결과 값을 최소로 만드는 문제이다. 해당 예제 55 - 50 + 40는 55 - (50 + 40)으로 괄호를 적용할 경우 최소가 된다. for문을 통해 문자인 숫자를 붙여주고, 처음에 나온 연산자가 + 일 경우에는 더해주고, 그 외에는 -를 해주는 것이 최소값이 된다. #include using namespace std; string str; int sol(string str) { int ret = 0; string s = ""; bool isMinus = false; for (int i = 0; i > str; cout

DP 문제이다. cache[i][0] = min(cache[i-1][1], cache[i-1][2]) + board[i][0];cache[i][1] = min(cache[i-1][0], cache[i-1][2]) + board[i][1];cache[i][2] = min(cache[i-1][0], cache[i-1][1]) + board[i][2]; 이 부분이 핵심이므로 디버깅 다시 해보면 될 것 같다. 1234567891011121314151617181920212223242526#include #include #include using namespace std; int board[1001][3];int cache[1001][3];int N; int main(int argc, char const *argv..

문제의 핵심은 순서대로 치즈를 먹는다 이다. S -> 1 -> 2 -> 3 -> ... -> N 이므로, S -> 1 찾으면 BFS를 끝내고, 1 -> 2, 2 -> 3 이런식으로 찾아가면 된다. 만약 못먹을 경우에는 dist만 큐가 빌때 까지 늘려주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #include using namespace std;class Node {public: int x, y, dist, level; Node() {}; Node(int _x, int _y,..

DP로 점화식만 알면 풀 수 있다. 1234567891011121314151617181920212223242526272829#include #include #define ll long longusing namespace std; int n, m, test;int cnt = 0;ll cache[40][40]; ll sol(int f, int h){ ll &ret = cache[f][h]; if (f == 0 && h == 0) { return 1; } if (ret != 0) return ret; if (f != 0) ret += sol(f - 1, h + 1); if (h != 0) ret += sol(f, h - 1); return ret;} int main(int argc, char const *ar..

문제에서 3가지의 연산이 있다./3, /2, -1 따라서 이 3가지의 경우로 DP로 풀면 된다. 1의 경우에는 만족하는 경우가 없으므로 0 --> cache[1] = 02의 경우에는 /2 or -1의 경우 만족하므로 --> cache[2] = 13의 경우에는 /3의 경우가 만족하므로 --> cache[3] = 1이다. 힌트에서 10의 경우에는 10 -> 9 -> 3 -> 1의 경우이다. sol(10-1) +1 의 경우가 답이 될 것이다. 10 - 1을 해서 9를 만들고 cache[9]에 저장된 값을 불러오면 최소 연산으로 1을 만들 수 있을 것이다. 4의 경우에는4 -> 2 -> 14 -> 3 -> 1이렇게 2가지의 경우가 있다. 따라서 sol(4 - 1) + 1 = sol(3) + 1 = 1 + 1 =..

DP 문제점화식만 잘 세우면 된다.DP[1] = 1DP[2] = 2DP[3] = 4 DP[4] = DP[1] + DP[2] + DP[3] = 7 이다. 따라서 점화식은 DP[i] = DP[i - 3] + DP[i - 2] + DP[i - 1] 이다. 1234567891011121314151617181920212223242526272829303132#include #include using namespace std; int cache[11];int T, N;int sol(int n) { int &ret = cache[n]; if (ret != -1) return ret; if (n == 1) return 1; if (n == 2) return 2; if (n == 3) return 4; ret = sol(..

벽 부수고 이동하기 1과 비슷한 문제이다. 이 문제는 K 인자가 추가되어 벽을 K개의 갯수만큼 부실 수 있다.1 문제에서는 1번만 부실 수 있으므로 visit 배열을 [2]까지만 잡았지만, 이 문제는 K번 부실 수 있으므로 visit[10] (1