jmmm_25

문제 설명 카카오 프렌즈 컬러링북 출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.) 그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자. 위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다. 입력 형식 입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조..

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

BFS 탐색으로 풀 수 있는 문제이다. 우선 (1,1)의 좌표에서 시작하여 board == 0 인 곳으로 이동을 한 뒤, 벽을 만나게 되면 now.broken이 0일 경우만벽을 부수고, 벽이 아닌 곳으로만 이동하면 되는 문제이다. 단, 벽은 1개까지만 부실 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include using namespace std;class Node {public: int x, y, dist, broken; Node() {}; Node(int _x, int..

dfs로 모든 경우를 다 탐색하면 된다. 숫자는 변하지 않으므로 고정시키고 연산자만 for문과 재귀로 다 쓰면 된다.다시 한번 풀기!!!최대, 최소값은 10억이므로 처음에 초기화를 시켜주었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include #define INF 1000000000#define ll long longusing namespace std; int N;int op[4];int number[12];ll int Max = -INF;ll int Min = INF; void dfs(int depth, ..

말 그대로 주사위가 동, 서, 남, 북 으로 굴려졌을 때 어떻게 옮겨지는지를 구현하면 된다.너무 노가다로 푼 것 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132#include #include using namespace std; int ..