본문 바로가기

알고리즘90

BOJ 1194 - 달이 차오른다, 가자 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다. www.acmicpc.net 제약조건(열쇠,문)이 추가된 플러드필 문제이다 처음엔 큐에 방문노드위치(cy,cx)와 비트마스크를 이용한 현재 key, 그리고 visited배열을 넘겨주면서 열쇠를 먹으면 false로 초기화된 visited를 다음 .. 2019. 8. 6.
BOJ 2098 - 외판원 순회 TSP https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net #include #include #include using namespace std; const int INF = 1e9; int n, w[16][16], dp[16][1 2019. 8. 6.
BOJ 11780 - 플로이드2 #include #include #include using namespace std; typedef unsigned long long ll; const int INF = 1e9; int dist[101][101]; int via[101][101]; int ks[101][101]; void reconstruct(int i, int j, vector& path) { //i->j 경유없이 가는 경우면 if (via[i][j] == -1) { path.push_back(i+1); path.push_back(j+1); return; } //i->j 경유점이 있다면 int w = via[i][j]; //w에 경유점 담아주고 reconstruct(i, w, path); path.pop_back(); reconstru.. 2019. 8. 6.
BOJ 12865 - 평범한 배낭 기본 knapsack문제다. int knapsack(int pos, int cap) // 가방의 남은 용량이 cap이고 pos~n-1번 물건을 고를 때 가치의 최대. 0번 물건~ n-1번 물건을 순서대로 참조하면서 1. pos번째 물건을 선택할 수 있을 경우 (물건의 무게가 cap보다 낮거나 같은 경우) ret = max(pos번째 물건을 선택하지 않은 경우, pos번째물건의 가치 + knapsack(pos+1, cap - item[pos].first) 2. pos번째 물건이 너무 무거워 선택할 수 없는 경우 ret = pos번째 물건을 선택하지 않은 경우 d[pos][cap]을 메모하며 dp하는 문제다. #include #include #include using namespace std; int n, .. 2019. 7. 29.

티스토리툴바