나 요리학원 출신임

문제를 읽어보면 그냥 BFS+시뮬레이션으로 풀면 될거같다 심지어 크기도 작다!! 악마->수연 이 순서대로 보내면 수연이가 갈 수 있는곳의 최단거리를 BFS로 구할 수 있다! 큐를 2개만들고 악마큐를 먼저 실행시키고, 수연이큐를 실행시키자 악마가 다음칸으로 갈 수 있는 조건은 .이거나 S이거나이고 수연이가 갈수있는 조건은 .이거나 D이다! 악마가 방문할때마다 *로 바꿔주고 수연이가 방문할때마다 S로 바꿔주면 답이 착하게 나온다!! 소스코드 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 5..

풀려고 생각하다가 끝난 문제였다 한시간이 넘도록 생각해도 못풀었다 ㅎㅎ 수학적 머리가 없는건가 우선 f,g 계수들의 gcd가 1이기 때문에 어딘가 p로 안나눠떨어지는 수가 하나씩은 나온다! f에서 그위치를 i / g에서는 j라고 해보자 f*g=h일때 h의 계수를 생각해보면 h^(i+j)의 계수는 f와g의 index합이 i+j인것들의 합이다 이 때 fi*gj도 포함되는데 이 수는 각각 p로 안나눠지므로 두 수의곱도 당연히 안나눠진다! 그래서 답은 그냥 안나눠지는 위치 두개를 찾아서 더하면 된다 수학적으로 증명해서 알려주면 참 쉬워보이는데 시간안에 어케해야할까 이걸..!! 수학은 어렵다..! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using nam..

메모리와 시간 때문에 많이 틀린 문제다 풀긴했지만 고칠 부분이 많은 코드같다..! 우선 문제를 보면 결국 딸 이름은 n+m-1의 길이를 가질것이다 그럼 시작점부터 해서 가중치가 제일 작은것만 골라서 끝점까지 가면 된다! 다익스트라! 사용하자 각 자리의 알파벳을 가중치라 생각하고 이름을 찾아가다가 n+m-1 길이의 이름을 찾으면 break를하자! 여기서 break안하면 pq에 너무 많이들어가서 메모리가 터진다 소스코드 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 #include u..

시간이 충분한 문제다 내가 0일 때 그리고 1일 때 경우를 나눠서 생각하면 된다 먼저 모양의 수는 어떻게 정할까? 유니온 파인드를 이용하면 쉽게 찾을 수 있다 merge할 때마다 해당 부모의 수도 합치면 된다 그렇게 미리 크기를 구해두고 모든 정점에서 만약 해당 정점이 1이면 해당 부모의 크기 0이면 4방향 부모의 합+ 1=>(나를 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 55 56 57 58 59 60 61 62 63 6..

사이클 중 가중치의 합이 가장 작은 사이클의 길이를 출력하는 문제다 N이 크면 다른방법을 쓰겠지만 N이 작아서 그냥 완탐을 돌렸다 모든정점에서 시작해서 해당 정점으로 돌아오는 사이클을 찾고 비교하면 된다 근데 이상하게 가지치기를 하니까 정답이고 안하니까 테케 3개가 틀린다 왜일까..! 가지치기 안해도 다시 시작점으로 돌아올 때 min값을 초기화하면 답이 나올거라고 생각했는데..! 아직 의문이다 ans>sum+cost 이 부분을 빼면 틀린다..! 아시는분..! 소스코드 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 #include using namespace std; #define ll ..

문제가 좀 복잡해 보이는데 잘 읽어보면 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..