문제가 좀 복잡해 보이는데 잘 읽어보면 dfs를 이용해서 풀 수 있다 먼저 입력으로 들어오는 이름들은 map을 통해 숫자롤 매겨주자 그리고 시너지가 발생하는 조합을 통해 그래프를 만들어준다 그래프를 다 만들었다면 이제 문제는 나와 연결된 정점과 다른색으로 색칠하며 dfs를 돌릴 수 있냐! 이걸로 바뀌게 된다 나와 연결된 정점들에 나와 다른색을 주면서 dfs를 돌아보자 만약 같은색이 있다면 false! 다 돌수 있다면 true 다 하나라도 false가 나오면 No가 답이다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 4..
입력받는 숫자들을 보면 엄청 작다 완탐으로 정말 다 찾아보면 된다 답이 여러개라면 숫자가 많은것 중에 사전순으로 앞에오는 것을 출력해야한다 따라서 각 자리마자 0~x까지 넣어보면서 햄스터 수를 만족하고 현재 답보다 합이 크다면 계속 바꿔주면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include using namespace std; #define ll long long int t,n,x,m; pair arr[11]; int maxcnt; int ans[11]; void solve(int pos,..
BFS를 돌려서 푸는 문제다 성을 넣지말고 반대로 모래를 넣으면 쉽게 풀 수 있다 모래를 기준으로 8방향을 보면서 성이 있다면 1씩 감소시켜준다 만약 성의 견고함이 0이 된다면 모래로 바꾸고 큐에 넣어주면 된다 풀긴 풀었는데 시간이 좀 너무 오래걸렸다.. 왜지..! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include using namespace std; #define ll long long int arr[1010][1010]; int dx[8]={-1,-1,-1,0,..
BFS를 이용해서 풀 수 있다 가로->세로 or 세로->가로 이렇게만 이동이 가능하다! 처음에 4방향 그대로 모두 check해줬더니 시간초과가 났다 근데 가로로 온다면 왼쪽에서 오든, 오른쪽에서 오든 똑같다 세로도 마찬가지다! 결국 가로 / 세로 나눠서 2방향으로 보면 시간안에 통과가 가능하다! 그렇게 하기 위해서는 하나는 0 하나는1로 생각하면 된다 4방향을 나누기 2만하면 0,1로 표현가능 하므로 그것만 바꿔주면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #..
dp를 통해 색칠해 나갈 수 있다 우선 흰색 검은색 가능한데 동시에 연결된 정점이 (검은색/검은색)은 불가능하다 그럼 이 부분만 잘 처리하면 dfs+dp를 통해 해결할 수 있다! 먼저 나의 색을 저장하고 내가 만약 흰색이라면 내 자식들을 (검은색으로 칠하는 경우 + 흰색으로 칠하는 경우)만큼 가능하고 검은색이라면 (흰색으로 칠하는 경우)만 가능하다 경우의 수 이기 때문에 각 자식들의 수의 곱을 구해가면 된다! long long 조심하자~~ 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include using namespace std..