104%

DFS를 활용하는 약간은 응용된 문제 그냥 단순히 바이러스인 2를 퍼트리는것 자체는 별로 어렵지 않다. 그냥 DFS혹은 BFS를 사용하면 된다.하지만 기둥인 1을 3개 세워야 하기 때문에 좀 생각을 해야 한다. 기둥을 3곳에 세워야 하는데 이거는 그냥 모든 경우의수를 다 해 보는 수 밖에 없다. 따라서 처음에 입력을 받을때 0인곳의 위치를 벡터에 넣어 놓고 나중에 그 벡터에 있는 값중 3개를 차례차례 중복되지 않게 꺼낸 다음그 세곳에 기둥을 세워 놓고 나서 DFS를 돌린다. DFS를 돌리면 바이러스가 퍼질것이고(2) 그리고 나서 안전 영역의 수를 카운트 하며, 안전 영역 크기의 최대값을 갱신한다. 위의 과정을 벡터에 있는 모든 0의 3개 조합에 대해서 전부 수행했을때의 안전영역의 최대값이 정답이 된다. ..

풀이 및 해설https://docs.google.com/document/d/1tY1X9U63XZ4EF7VQIjWltnzFvgo3bsyQriNdN2cCzRY/edit?usp=sharing

예전에 풀었던 문제인데 O(n2)방식이 아닌 O(NLOGN)방식으로 다시 풀어봤다. 벡터에는 최장 길이 부분 수열이 만들어 진다. 값이 들어있는 배열을 처음부터 끝까지 반복해 가면서 현재 인덱스의 원소가 벡터안에 어느 위치에 들어가야 하는지를 찾아서 그곳에 값을 넣어주는 방식이다. 자세한 내용은 아래 링크에 있으니 먼저 문서를 보고 나서 코드를 보면 이해가 갈것이다.클릭 1234567891011121314151617181920212223242526272829303132333435363738#include #include using namespace std; vector vt;vector::iterator it;int arr[1000]; vector::iterator find(int x){ for(it=v..

플로이드 알고리즘어떤 정점에서 시작해서 다른 정점으로 가는 최단경로를 구함. (모든 정점에 대해서) 알고리즘 동작 과정 0번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로1번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로2번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로3번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로4번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로5번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로6번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로를 모두 구할것이다. 처음에는 0번 정점만을 거칠수 있을때 0번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로1번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로2번에서 0,1,2..

기본 DFS문제 1인곳부터 dfs를 시작하되 방문한곳은 0으로 바꿔놓는다. dfs를 시작하는곳에서 count를 증가시켜준다. 소스코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include using namespace std;vector result;bool input[51][51];int n,m;int diffx[8] = {-1,0,1,-1,1,-1,0,1};int diffy[8] = {1,1,1,0,0,-1,-1,-1}; void dfs(int x,int y){ if(xn || ym)return; if(input[x][y] =..

이 문제도 if else떡칠만 하면 되는 쉬운문제인데 약간 함정을 파놓았다.숫자가 0~9만 되는게 아니라 10까지도 된다는것과 스타상을 받으면 바로 전 숫자까지 2배를 시켜줘야 한다는점 등등.. 문제 자체는 쉬운데 풀다가 계속 디테일을 놓쳤다 이것도 한 20분좀넘게 걸린거 같다 시간을 줄이자..문제 이해하는게 더 오래걸린듯 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include #include #include using namespace std;vector result; int main(){ string str; cin>>st..

풀긴 풀었는데 여러번 수정해서 풀었다.. 시간을 좀 줄여야겠다 나는 비트연산으로 안풀고 스트링으로 풀었다 근데 다시 생각해보니까 정수 두개를 비트연산 | 해주고 나서 1인지 0인지 체크해서 # 또는 공백으로 바꾸는 방법도 있겠다. 이 문제 푸는데 거의 20~30분 걸린거 같다. 좀더 시간을 줄이자 다음에 비트연산으로 다시 풀어보자. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include#include#includeusing namespace std; int n;int arr1[17];int arr2[17];vector strv;string convert(in..

요즘 문제 풀면서 느끼는건데 실력이 좀 는거같다 내가 생각한대로 알고리즘 짜면 테스트 케이스는 웬만하면 다 나오는편인것 같아서 뿌듯하다. dp[i][1] -> i 번째 열의 첫번째 행 원소를 택하는 경우dp[i][2] -> i번째 열의 두번째 행 원소를 택하는 경우dp[i][3] -> i번째 열의 원소를 아무것도 선택하지 않는 경우 를 나타낸것이다. dp[2][1] -> 1행 2열의 원소를 택했을때 얻을수있는 최대 점수 -> 30을 택하고 20을 택하면 되므로 50dp[2][2]- > 2행 2열의 원소를 택했을때 얻을수 있는 최대 점수 -> 40을 택하고 10을 택하면 되므로 합이 50dp[2][3] -> 2열의 원소를 아무것도 택하지 않았을때 최대 점수 -> 그열의 전열까지의최대점수 ->dp[1][1]..