하다보니

문제) 연속된 3개의 계단을 밟지 않고 한 번에 한 계단, 또는 두 계단을 올라 마지막 도착 계단에 도달할 때, 얻을 수 있는 총 점수의 최댓값 해결 방법) DP , 작은 하위 문제로 큰 문제를 해결한다. DP 해결 방법 1. 테이블 정하기 2. 점화식 구하기 3. 초기값 구하기 ''' 1. 테이블 정의하기 d[i]=i번째 계단을 밟을때 얻는 최대값. 2. 점화식 d[i]=d[i-1]+c[i] d[i]=d[i-2]+c[i]의 max 2. 초기값 d[0]=0 d[1]=c[1] ''' n=int(input()) c=[0] for i in range(n): x=int(input()) c.append(x) d=[0]*(n+1) d[1]=c[1] for i in range(2,n+1): d[i]=max(d[i-1..

#include #include #include using namespace std; int n;//총 n 명. n을 반반씩 나눠서 팀을 나눈다. int board[25][25]; int main() { cin >> n; for (int i = 0; i > board[i][j]; } } vector team(n); fill(team.begin() + (n / 2), team.end() , 1); int mn = 0x7f7f7f7f; do { int diff = 0; for (int i = 0; i < n-1; i++) { for (int j = i + 1; j < n; j++) { if (team[i] != team[j]..

#include #include using namespace std; int n;//시험장 개수 vector people; int b, c;//총감독관 감시 응시자수, 부감독관 감시 응시자 수 int main() { cin >> n; for (int i = 0; i > x; people.push_back(x); } cin >> b >> c; long long tot=0; for (int i = 0; i < n; i++) { if (people[i] - b

#include #include #include #include #define X first #define Y second using namespace std; int n, m; pair red, blue; // 빨간 구슬과 파란 구슬의 위치 string board[11]; // dist[a][b][c][d] : 빨간 구슬이 (a, b)이고 파란 구슬이 (c, d)에 위치한 상황에 도달하기 위한 동작의 횟수 int dist[11][11][11][11]; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { 1, 0, -1, 0 }; int bfs() { queue q; q.push({ red.X, red.Y, blue.X, blue.Y }); dist[red.X][red.Y][bl..

/* 뱀이 나와서 기어다닌다. 사과를 먹으면 뱀 길이가 늘어난다. 벽이나 자기 자신의 몸과 부딪히면 게임 끝. nxn 정사각 보드 위에서 진행. 몇몇 칸에는 사과가 놓여져 있다. 뱀의 길이는 1이다. 처음엔 오른쪽을 향한다. */ #include #include #define X first #define Y second using namespace std; int n;//보드의 크기 int k;//사과의 개수 int board[105][105]; int dx[4] = {0,1,0,-1}; int dy[4] = {1,0,-1,0}; int vis[105][105]; queue snake; queue tail; int main() { cin >> n; cin >> k; //사과의 위치 for (int i =..

#include using namespace std; int board[25][25]; int ndice[6]; int dice[6]; int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1,0,0 }; void go(int dir) { //동:1 서:2 북:3 남:4 switch (dir) { case 0: ndice[0] = dice[0]; ndice[1] = dice[4]; ndice[4] = dice[3]; ndice[5] = dice[1]; ndice[2] = dice[2]; ndice[3] = dice[5]; break; case 1: ndice[0] = dice[0]; ndice[1] = dice[5]; ndice[2] = dice[2]; ndice[3] = dice..

#include #include #include using namespace std; deque dq[4]; void go(int num,int dir) { int dirs[4] = {}; dirs[num] = dir; int idx = num; //왼쪽으로 전파 while (idx > 0 && dq[idx][6] != dq[idx - 1][2]) { dirs[idx - 1] = -dirs[idx]; idx--; } idx = num; //오른쪽으로 전파 while (idx < 3 && dq[idx][2] != dq[idx + 1][6]) { dirs[idx + 1] = -dirs[idx]; idx++; } for (int i = 0; i < 4; i++) { if (dirs[i] == 1) { dq[i..

/* 수와 수 사이에 끼워넣을 수 있는 n-1개 연산자 있음. n개 숫자 있음. 숫자는 변경 불가. 식의 계산은 연산자 우선 순위를 무시하고, 앞에서부터 진행되어야 한다. 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 양수로 바꾼 후 몫을 음수로 한 것. */ #include #include #include using namespace std; int n,x; int num[15]; int num_copy[15]; vector oper; int result; //차례대로 +:0 -:1 x:2 %:3 개수 int cal(int x,int y,int op) { if (op == 0) { return x + y; } if (op == 1) { return x - y; } if (op == 2..

/* 연구소에 벽을 세우려고! nxm 직사각형. 바이러스는 상하좌우 퍼져나감 새로 세울 수 있는 벽의 개수 3개. 꼭 3개 세워야 함. 0은 빈칸, 1은 벽, 2는 바이러스 안전영역 크기의 최댓값. 문제 풀이 방법 - 우선 빈칸중에 벽을 세울 수 있는 3개의 조합을 구한다. - 해당 경우에 따라 벽을 세워서 2가 퍼져나가는 것을 구하고 - 빈칸의 개수를 세어 안전영역을 구한다. -> 최댓값. */ #include #include #include #include #define X first #define Y second using namespace std; int n, m;//세로 크기 n과 가로 크기 m int board1[10][10];//원본 int board2[10][10];//복사본 vector ..

/* 2048 문제 - 게임판을 상하좌우로 기울인다. 5번 기울여서 최대값을 고른다. -> 모든 경우의 수를 다 확인. - 게임판을 기울이면 숫자가 기울면서 합쳐진다. -> 상하좌우는 게임판을 돌려서 구현하고, 기울여서 합쳐지는 함수 */ #include #include using namespace std; int n;//한변의 길이 int board1[25][25];//입력받는 원본 게임판 int board2[25][25]; //복사하여 최대값을 구하려는 것 void rotate() { int tmp[25][25]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) tmp[i][j] = board2[i][j]; for (int i = 0; i < n; ..