전체 글

코드#include using namespace std;int n,k,a[103], dp[10003];int main() { cin >> n >> k; dp[0] = 1; // 0원을 만드는 경우의 수는 1 for(int i = 0; i > a[i]; for(int i = 0; i 풀이j가 a[i] 이상이어야 a[i]원부터 시작해서 k까지의 값을 대상으로 할 수 있다. dp[j]는 j원을 만들 수 있는 경우의 수를 의미한다. 그리고 dp[j - a[i]]는 j - a[i]원을 만드는 경우의 수를 의미한다. 만약 j - a[i]를 만들 수 있다면 a[i]원 동전을 이용해서 j를 만들 수 있다. 따라서 j원을 만드는 경우의 수에 j - a[i]원을 만들 수 있는 경우의 수를 더해준다.

코드#include #include using namespace std;int t,w,a[1003], dp[3][32][1003]; // 상태 3개 필요int go(int loc, int cnt, int idx) { if(cnt > w) return -987654321; // 움직이는 횟수가 넘은 경우 if(idx == t) return 0; if(dp[loc][cnt][idx] != -1) return dp[loc][cnt][idx]; // 3-loc을 하면 1또는 2가 나온다 int move = (a[idx] == loc ? 0 : 1) + go(3 - loc, cnt + 1, idx + 1); int stop = (a[idx] == loc ? 1 : 0) + ..

코드#include #include #include using namespace std;int n, happy[23], sad[23],dp[23][103];int go(int idx, int hp) { if(hp > n; memset(dp, -1, sizeof(dp)); for(int i = 0; i > sad[i]; for(int i = 0; i > happy[i]; cout 풀이0 - 1 냅색문제랑 비슷한 유형이다. 인사를 하거나 하지 않는 경우를 나눠서 생각했다. 인사를 한다면 체력을 깎고 행복을 올린다. 인사를 하지 않으면 다음 케이스로 넘어간다. 만약 체력이 0이하가 되면 매우 작은 값을 리턴한다. 마지막 사람까지 만난 경우, 체력이 남아있을 때 최대 행복을 출력한다.

코드#include #include #include using namespace std;int n,m,dp[53][53],visited[53][53];string s;char a[53][53];// H는 구멍, 구멍이나 밖으로 나가면 게임 끝// 왼쪽 위는 숫자// 무한번 움직일 수 있는 경우는 -1 출력 -> 어떻게 찾지int go(int x, int y) { if(x >= n || y >= m || x 사이클 생성 exit(0); } int move = a[x][y] - '0'; visited[x][y] = 1; // 방문처리 int u = go(x - move, y) + 1; int d = go(x + move, y) + 1; int l = go(..

코드#include #include #include using namespace std;int n, a[18][18], dp[18][18][4]; // 상태값은 3개: x좌표, y좌표, 방향// 1은 가로, 2는 세로, 3은 대각선int go(int x, int y, int dir) { if(x >= n || y >= n || (a[x][y] == 1)) return 0; // 벽인지 아닌지 확인 // 대각선으로 움직이는 경우는 추가 확인 필요 if(dir == 3 && (a[x - 1][y] == 1 || a[x][y - 1] == 1)) return 0; if((x == n - 1) && (y == n - 1)) return 1; // 목표지점 도달 if(dp[x][y][..

코드#include #include #include using namespace std;int n,tmp;stack stk;vector v;vector res;int main() { cin >> n; for(int i = 0; i > tmp; v.push_back(tmp); } int num = 1; for(int i = 0; i o)) { cout 풀이스택 연산을 통해 주어진 수열을 만들 수 있는지 확인하는 문제이다. while 반복문 안에서 스택의 top이 현재 목표 값인 o와 같다면 결과에 -를 추가하고 반복문을 종료한다. 스택이 비어 있거나 top이 o보다 작으면 스택에 num을 push하고 결과에 +를 추가한 후 num을 1 증..

코드#include #include using namespace std;const int MAX_N = 303;const int dx[] = {-1,1,0,0};const int dy[] = {0,0,1,-1};int n,m,a[MAX_N][MAX_N],b[MAX_N][MAX_N],visited[MAX_N][MAX_N],res;// 덩어리 판단 로직void dfs(int x, int y) { visited[x][y] = 1; for(int i = 0; i = n || ny >= m || nx = n || ny >= m || nx > n >> m; for(int i = 0; i > a[i][j]; } } // 녹이고, 개수 확인 res = 0; while(..

코드#include #include using namespace std;int n,a,b,m,x,y,visited[103];vector adj[103];void dfs(int x, int depth) { visited[x] = depth; for(int i : adj[x]) { if(visited[i] == -1) { dfs(i, depth + 1); } } return;}// 촌수 -> 깊이int main() { cin >> n; // 전체 인원 cin >> a >> b; // 촌수 계산할 사람 cin >> m; fill(visited, visited + 103, -1); for(int i = 0; i > x ..

코드#include #include using namespace std;int f,s,g,u,d, visited[1000004],res = -1;// 적어도 -> 최단거리. 1차원 배열에서의 최단거리// 가중치가 없으므로 bfs 사용// 1번도 안움직여도 되는 경우가 있음// res는 -1로 초기화int main() { // f는 최대 높이, s는 현위치, g는 목표지점, u위 d 아래 cin >> f >> s >> g >> u >> d; queue q; q.push(s); visited[s] = 1; while(q.size()) { int pn = q.front(); if(pn == g) { res = visited[pn] -..

소수점 고정 시 반올림 오류#include using namespace std;int main() { cout cout  C++의 cout 객체와 precision 설정은 반올림 오차가 발생할 수 있는 방법으로 동작한다. 이는 숫자 내부 표현 방식과 관련이 있다. 실수는 이진 부동 소수점 형식으로 저장되기 때문에 10진수에서 정확하게 표현할 수 없는 경우가 생길 수 있다.  3.15는 3.1로 출력된다.이는 반올림 오차로 인해 3.149999... 와 같이 표현될 수 있고, 소수 첫째 자리까지 표시할 때 3.1로 반올림 된다.4.15는 4.2로 출력된다.이 경우 4.1500000... 과 같이 표현되어 소수 첫째 자리까지 표시할 때 4.2로 반올림 된다.부동 소수점 방식 오차부동 소수점 방식은 고정 소..