노는 게 제일 좋아

DFS + DP 문제다. 나는.. DP를 까먹고 있어서 답을 결국 봐버렸다.ㅠㅠ 어쩐지.. 이 문제는 중요해보였다. 아니 우선 나에게 통찰력을 주었다. https://www.acmicpc.net/submit/12869/48753292 #맞은 풀이 #include using namespace std; //재귀만 해보려는데 도저히 생각이 안나서...답을 찾았다. int dp[61][61][61]; //DP를 사용하라는데.. 재귀 + DP란다. //scv 체력 a,b,c에 대해서 각 공격을 적용해본다. int func(int a, int b, int c){ //죽은 scv에 대해서는 연산하지 않는다. //이 처리를 하는 이유는 음수에 대한 계산을 하지 않기 때문이다. if(a> N; //배열 모두 초기화 me..

BFS + DP 문제다. 사실 DP란 것은 아니고.. 그냥 상태 저장문제라고 보면 된다. 즉, 이전의 작은 값을 보장하면 그것들의 합이 최소라는 것에 대해선 DP라고 볼 수 있다. https://www.acmicpc.net/problem/4485 #맞은 풀이 #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int cave[126][126]; int main(){ int cnt = 0; while(1){ cnt++; int n; cin >> n; if(n == 0)break; int dp[126][126]; //행:r 열:c for(int r = 0; r cave[r][c]; dp[r][c] = INT_MAX; } ..

은근히.. 헷갈렸다. 사실 쉬웠는데.. 헷갈렸다. 짜증난다 ㅠㅠㅠ BFS문제면서 DP 문제라고 생각하면 되겠다. https://www.acmicpc.net/problem/16928 #맞은 풀이 #include using namespace std; vector fromTo; //보드 int dist[101]; //array[출발]=도착 int arr[101]; int main(){ int N, M; cin >> N >> M; for(int i = 0; i> start >> finish; arr[start] = finish; } //배열초기화(시작주소, 종료주소(얼만큼 할지), 값) fill(dist, dist+101, -1); //1부터 BFS로 시작 dist[1] = 0; queue q; q.push(1..

BFS 중에서 가장 재밌는 유형이면서 가장 까다롭다. 조건이 별로 없어서 다행이지.. 여러개면 진짜 한없이 어려워진다. 가장 중요한 문제가 아닌가 싶다. 이 문제를 잘 풀줄 알면.. 다른 것도 잘풀 걸..? https://www.acmicpc.net/problem/5427 #맞는 풀이 #include using namespace std; int dc[4] = {-1,1,0,0}; int dr[4] = {0,0,-1,1}; char board[1002][1002]; int test[1002][1002]; //불 위치, 0 빈공간, -1 불이 갈 수 없는 공간 int live[1002][1002]; //상근이 탈출 int main(){ int testcase; cin >> testcase; //맵이 크기 상..

이것도 재밌고 문제로 나오지 않을까? 싶다. https://www.acmicpc.net/problem/2146 #맞은 풀이 #include using namespace std; #define X first #define Y second int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N; int conti[100][100]; int area[100][100]; int dist[100][100]; int flag = 1; int minDist = INT_MAX; void DFS(int x, int y){ area[x][y] = flag; for(int dir = 0; dir= N || ny = N)continue; if(area[nx][ny]..

어렵지 않았다. 다만 어떻게 풀지? 가 관건이다. https://www.acmicpc.net/problem/14226 문제 분석부터 해보자 최솟값을 가지는데 수행해야 하는 작업의 가중치가 같다? BFS 가자 #include using namespace std; //1개는 이미 입력 int S; int visited[3000][3000]; int main(){ cin >> S; //현재 상태, 클립보드에 저장된 개수 queue q; q.push({1,0}); visited[1][0] = 1; while(!q.empty()){ auto cur = q.front(); q.pop(); int now = cur.first; int clip = cur.second; //체크 if(now == S){ cout

나의 좁은 식견에 안타까워하며 배운 상태 저장방법!! 행렬을 문자열로 문자열을 행렬로 변환하는 방법!! 행렬 자체를 저장하는 것이 메모리가 많이드므로 문자열로 저장하는 방법!!! 배울 것이 많은 문제다. https://www.acmicpc.net/problem/1525 #맞은 풀이 #include using namespace std; int dc[4] = {1,-1,0,0}; int dr[4] = {0,0,1,-1}; string start = ""; //상태를 문자열로 저장함 int answer = -1; //answer가 갱신되지 않는 것은 아무리 시도해도 만들 수 없는 것을 의미 int main(){ queue q; //string(상태), int(실행횟수) set check; //상태가 중복되는 ..

조금 특이한 BFS랄까..? 최장거리의 최단시간을 구해야 한다. ???? 처음에는 이해가 안갔다. https://www.acmicpc.net/problem/2589 #맞는 풀이 #include using namespace std; int row, col; //행, 열 char arr[50][50]; //입력 int visited[50][50]; //방문여부 -1로 초기화 int memo[50][50]; // 기억 int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int main(){ cin >> row >> col; //문자열로 입력받음. for(int i = 0; i> s; //visited -1 초기화 for(int j = 0; j

이런 문제를 싫어하지만.. 자주 나오는듯 하다. 내용이 많아서 어려운 문제다. 게다가 6초나 준다.. 시간이 얼마나 많이 걸릴 지 예상이 가는 문제다. https://www.acmicpc.net/problem/9019 #맞은 풀이 #include using namespace std; const int MAX = 10000; int A,B; bool visited[MAX]; int main(){ int T; cin >> T; //테케 while(T--){ cin >> A >> B; //초기화 for(int i = 0; i

음.. 처음 생각하기 정말 어려웠다. 어떻게 BFS로 푼다는 거지..? BFS는 모든 단계 탐색이 비용이 같아야하는데.. 쟤는 0초인데?? 우선순위 큐를 쓰라는 말을 들어도 못알아듣다가 다른 분의 코드를 조금 보고나서야 알았다. https://www.acmicpc.net/problem/13549 #맞은 풀이 #include using namespace std; int N, K; bool visited[100002]; int main(){ cin >> N >> K; //왜 우선순위 큐를 사용해야하느냐?? //+1,-1의 노드를 탐색하는 것과 *2 노드를 탐색하는 것은 다르다. //즉, *2를 하는 것은 할 수 있는 만큼 하고 +1과 -1을 해야한다. //즉, 단계도 단계지만 시간으로 구분되어야 한다. //..