옛날에 풀어본 문제여서 다시 풀어보려고 했는데 탈탈 털렸다 옛날에는 어떻게 풀었을까? 도움을 받았었나 ㅎㅎ 이 문제는 하이퍼링크는 연결되어있기 때문에 안에서는 비용이 안들고 하이퍼링크를 넘어갈 때는 비용이 든다는걸 그래프로 표현해야한다 어떻게 해야할까..! 그래프를 만들때 (N+M)개의 정점으로 만들어주면 된다! 1~N 까지는 정점이고 (N+1 + M)까지는 바로 하이퍼링크..! 내가 어떤 점 X 가 하이퍼링크 K에 속해있다면 그래프 X에서는 갈 수 있는 하이퍼링크 K에 연결시켜주고 1의 비용이 들고 반대로 하이퍼링크 K 에서는 갈 수 있는 점들 X를 연결하고 하이퍼링크 안에서 이동이므로 비용은 0이 된다! 그래서 그래프를 만들면 X -> K (비용 1) 하이퍼링크 밖에서 이동 (정점 X를 가진 하이퍼링..
오래 고민한 문제다..! 이런거 참 생각을 잘 못하는거같다 어떤 화분을 깨면 화분에 해당하는 숫자가 오른쪽에 임의에 화분에 있다면 그 화분도 깰수있다 계속 연속적으로 이어져간다 자 생각을 해보자..! 맨 처음 화분은 무조건 깨야만한다. 안그러면 아무도 깨주지 않으므로..! 그럼 맨 처음 화분에 포함되는 수를 앞으로 만난다면 그 화분도 무조건 깨져야한다 그럼 입력받으면서 처리할 수 있다..! 화분을 깨지는 수를 계속 저장해가며 하나라도 가지고 있으면 깨버리자! 소스는 참 짧다! 처음에는 set을 썼는데 그럼 시간이 너무 오래 걸린다 배열을 이용하자 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include using namespace std; #define ll long..
참 어려워 보이는 문제다 근데 생각해보면 쉬운 문제다 물론 long long 안써서 처음에 틀렸다 ㅎㅎ 먼저 우리가 알아야할 x들은 소수라는 점을 기억하자 그럼 c1,c3,c5,c6은 소수 2개의 곱이므로 유일한 수 2개가 있을 것이다. 결국 완탐하면 된다! 이 문제에서 x4랑 x8은 의미없다 쓰지 않는다 완전탐색을 할 때 어떤 수 2개를 곱해서 c가 되야하므로 i*ic1>>c2>>c3>>c4>>c5>>c6; vector x1,x2,x3,x4,x5,x6,x7,x8; solve(c1,x1,x2); solve(c3,x6,x7); solve(c5,x2,x3); solve(c6,x6,x5); for(int a=0;a
수학 공부 열심히 한다는 마음으로 항상 틀리며 공부하고있다 ㅎㅎ 이 문제를 풀 때 혼자 너무 어렵게 접근해서 처음에는 반도 못갔다 코포 끝나고 혼자 풀어보니까 f(a,b) = a&(-b) 로 정리된다는걸 깨달았다 근데 거기서 발전은 못해서 에디토리얼을 봤다 ㅎㅎ 어렵다..!! 결국 a1~an까지 정리하면 a1&(-a2)&(-a3)&(-a4)...&(-an)이 된다는 걸 알 수 있다 그럼 여기서 주목할 건 내가 어떤 2^k 승의 비트를 가지는 수가 1개라면 그걸 a1에 놨을 때 나머지 a2~an까지 -가 붙기 때문에 2^k 위치를 살려준다! 예를들어 2^5 비트가 1인 수가 딱 1개만 있고 그걸 a1에 둔다면 나머지 수들은 2^5가 0이지만 -가 붙어서 1로변하고 a1에 놓인 2^5가 계속 1일 수 있다 ..
이런 수학문제가 참 어려운거같다 나는 한참 생각하고 틀린 문제다 혼자 식을 줄이려고 애썼는데 안떠오른다.. 이 문제는 m이 1000이하인게 힌트다! 먼저 2가지 경우가 있을 수 있다 1. nm인 경우 이 경우를 생각도 못했다. 만약 n>m이라면 어떻게 될까? %m해서 나올 수 있는 값은 총 m개다 근데 m보다 큰 n에 대해 %m을 한다면 비둘기집의 원리에 의해 누군가 하나는 같은게 나올 수 밖에 없다!! 생각도못함..! 같은게있다는말은 빼면 0이된다는 말이고 결국 곱하기 0이 생긴다는거니까 0이다 그냥! 그냥 0..! 수학공부를 다시 해야할까보다.. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace ..
문제를 읽어보면 그냥 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 ..